Haskell 中的 scanl 如何在 Either 列表上工作 - 两种情况的比较

Question

我正在尝试使用 Haskell 中的

scanl

函数。我已经缩小了我的问题范围，可以在以下两种情况下描述，可以使用 Haskell 中包含

scanl

的普通库在解释器中运行（请注意，我不一定对这里的 Monadic 值感兴趣，但只是如何使用

scanl

来确保类型一致性）：

为什么以下与预先列出的

Right value

的工作有效：

*Defs> scanl (\x acc -> x ++ acc) [] [[(Right 1)], [(Right 2)]]  
[[],[Right 1],[Right 1,Right 2]]

当这不起作用并导致以下错误消息时：

*Defs> scanl (\x acc -> [x] ++ acc) [] [(Right 1), (Right 2)]

<interactive>:36:35: error:
    * Couldn't match expected type `[[a]]'
                  with actual type `Either a0 b0'
   ...

Answer 1

我认为你已经交换了值和累加器。考虑

scanl

的类型：

ghci> :t scanl
scanl :: (b -> a -> b) -> b -> [a] -> [b]

累加器值的类型为

b

。它是第一位的。

如果你交换第二个例子中的参数，它会起作用：

ghci> scanl (\acc x -> acc ++ [x]) [] [(Right 1), (Right 2)]
[[],[Right 1],[Right 1,Right 2]]

您还可以交换第一个示例的参数，这也有效：

ghci> scanl (\acc x -> acc ++ x) [] [[(Right 1)], [(Right 2)]]
[[],[Right 1],[Right 1,Right 2]]

Answer 2

你在这里要做的事情已经存在，这是

inits :: [a] -> [[a]]

，它会产生所有前缀。您使用列表的列表，但可以通过连接而不是假装来处理它。

每次构建一个附加在右端的新列表都需要 𝓞(n²)，这是有道理的，因为整个构建确实是 𝓞(n²)。但我们可能只想生成最后的列表。

因此，最好使用差异列表，它允许在 𝓞(1) 中追加一个元素，因此如果我们只想构造，最终只需要 𝓞(n²) 时间例如最后一项：

dapp :: [a] -> ([a] -> [a]) -> [a] -> [a]
dapp [] f = f
dapp (x : xs) f = dapp xs (f . (x :))

dground :: ([a] -> [a]) -> [a]
dground = ($ [])

因此我们可以将函数构造为：

ourInits :: [[a]] -> [[a]]
ourInits = map dgroup . scanl (flip dapp) id