首页 文章

使用foldl'，foldr列出串联

提问于
浏览 次
3

我现在正在学习Haskell，我遇到了以下问题：

我想用foldl'和foldr重写函数 . 我用foldr完成了它：

myConcat xs ys = foldr (:) ys xs

我可以't do it using foldl' . 我在RealWorldHaskell中读过，折叠器对于做这种事情非常有用 . 好的，但是可以't I also write an equivalant to ++ using foldl? Can someone show me how I can do this (if it can be done... The book doesn'提及它的任何事情）...

Haskell的类型机制阻止我这样做吗？我每次尝试都会遇到类型错误...

ghc haskell

5 回答

  • 2

    我猜你得到的错误是试图简单地将 foldr 切换到 foldl' ：

    myConcat xs ys = foldl' (:) ys xs

    产生错误（使用我的Hugs REPL）：

    ERROR - Type error in application
*** Expression     : foldl' (:) xs ys
*** Term           : (:)
*** Type           : a -> [a] -> [a]
*** Does not match : [a] -> a -> [a]

    请注意 [a] 和 a 的位置位于相反位置的最后两行（提供的类型和预期类型） . 这意味着我们需要一个类似 (:) 的函数，但它的参数顺序相反 .

    Haskell有一个为我们执行此操作的函数： flip 函数 . 基本上， flip 相当于

    flip :: (a -> b -> c) -> (b -> a -> c)
flip f y x = f x y

    也就是说， flip 将二进制函数作为参数，并返回另一个二进制函数，其参数与原始参数相反（"flipped"） . 因此，虽然 (:) 的类型为 a -> [a] -> [a] ，但我们看到 flip (:) 的类型为 [a] -> a -> [a] ，使其成为 foldl' 的完美候选参数 .

    使用 flip ，我们现在有了这个代码：

    myConcat xs ys = foldl' (flip (:)) ys xs

    这是因为 foldl' 的类型为 (a -> b -> c) -> a -> [b] -> c

    使用参数 [1..5] 和 [6..10] 运行它，我们得到 [5,4,3,2,1,6,7,8,9,10] 的结果，这几乎是我们想要的 . 唯一的问题是第一个列表在结果中向后转 . 添加对 reverse 的简单调用为我们提供了 myConcat 的最终定义：

    myConcat xs ys = foldl' (flip (:)) ys (reverse xs)

    查看此过程显示了编写Haskell代码时常常出现的一个好处：当遇到问题时，您可以一次解决一个（小）步骤 . 当您已经有一个正在运行的实现，并且您只是尝试编写另一个实现时，尤其如此 . 需要注意的一件事是，如果更改实现的一部分（在这种情况下，将 foldr 更改为 foldl' ），那么许多其他所需的更改将完全脱离类型定义 . 剩下的少数是纠正问题，可以通过运行测试用例或查看所用函数的确切性质来轻松找到 .

    PS：任何能够梳理最后一行代码的Haskell家伙都可以自由地这样做 . 虽然它并不可怕，但我觉得它不是很漂亮 . 不幸的是，我对Haskell还不是那么好 .

    回复于
  • 9

    : 运算符将单个元素（左边的参数）连接到列表，右边的参数 .

    foldl 的参数是，

    • 折叠功能

    • 初始值

    • 要逐步执行的值列表 .

    回想一下，折叠函数作为其左参数采用当前值，该值以初始值开始 . 因此，折叠函数的左参数是一个列表，其右参数是单个值 . 如果你玩它，你可以得到像[只需切换参数以使类型匹配]，

    > foldl (\x y -> y:x) [1, 2, 3] [4, 5, 6]
[6,5,4,1,2,3]

    但是，这不是必须自己解决的;我能够使用 foldl 构建一个反向函数并将其称为子例程 - 但如果可以的话，可以随意解决它 .

    回复于
  • 3

    它并不总是可能，因为 foldr （以及 ++ ）在无限列表上工作，但 foldl 不能 . 但是， foldl 可以用 foldr 编写：http://www.haskell.org/haskellwiki/Foldl_as_foldr

    更新：对于有限列表， foldr 也可以用 foldl 编写：

    foldr :: (b -> a -> a) -> a -> [b] -> a
foldr f a bs =
  foldl (\g b x -> g (f b x)) id bs a

    所以你可以用 foldl 实现 (++)

    回复于
  • 9
    data [] a = ... | a : [a]
(:) :: a -> [a] -> [a]

    （）op对待左右操作数的方式不同 .

    a :: Char
b :: Char
c :: [Char]

    a:[b] 没问题

    a:b 不行

    a:c 没问题 .

    找到 foldr (:) 和 foldl (:) 的类型签名，你会发现它们的不同 .

    回复于
  • 4

    您可以使用foldl来完成它，但与基于foldr的实现相比，它不会有效

    使用foldl的示例：

    show $ (\xs ys -> foldl­ (\s e -> e:s ) ys (reve­rse xs)) [1,2]­ [3,4]
    回复于

相关问题