如何使用 foldl 编写 takeWhile？

Question

所以我正在做现实世界 haskell 书中的练习，我使用 foldl 为 takeWhile 函数编写了以下代码。

myTakeWhile' :: (a->Bool) -> [a] -> [a]
myTakeWhile' f xs = foldl step [] xs
    where step x xs | f x       = x:(myTakeWhile' f xs)
                    | otherwise = []

这给出了以下错误，我无法理解。

Couldn't match type ‘a’ with ‘[a]’
      ‘a’ is a rigid type variable bound by
          the type signature for myTakeWhile' :: (a -> Bool) -> [a] -> [a]
          at p1.hs:17:17
    Expected type: [a] -> [a] -> [a]
      Actual type: a -> [a] -> [a]
    Relevant bindings include
      step :: a -> [a] -> [a] (bound at p1.hs:19:11)
      xs :: [a] (bound at p1.hs:18:16)
      f :: a -> Bool (bound at p1.hs:18:14)
      myTakeWhile' :: (a -> Bool) -> [a] -> [a] (bound at p1.hs:18:1)
    In the first argument of ‘foldl’, namely ‘step’
    In the expression: foldl step [] xs

Answer 1

Edit

1) 你的主要错误是你不理解 fold 为你递归，你不必自己引用函数 myTakeWhile'，另外，fold 还有另一个类型：

foldl: (b -> a -> b) -> b -> [a] -> b

你在 where 子句的 step 函数中的类型错误就是因为它。

2) 你的第二个错误，因为 foldl 的定义，你的 takeWhile 会从头到尾创建，所以，你应该反转列表 （这一切只是因为你问的是如何用 foldl 做）

您可以使用简单的 lambda 和 if else 来做到这一点，可读性更高：

myTakeWhile' f xs = foldl (\rs x -> if f x then x:rs else []) [] (reverse xs)

示例：

myTakeWhile' (<10) [1..20]

[1,2,3,4,5,6,7,8,9]

然而，有了这个，你就不能像这样遍历无限列表：

myTakeWhile' (<10) [1..]

它会在尝试创建所有未计算的表达式时挂起。

无论如何，如果你想使用guards和where，你应该这样做：

myTakeWhile f xs = foldl step [] (reverse xs)
  where step rs x | f x = x : rs
                  | otherwise = []

3) 最重要的是：

正如@amalloy 所说，如果使用 foldr 来实现 takeWhile 更合适 :)。了解两者之间的差异在某些情况下至关重要，其中一个或另一个可能会导致您性能问题，为此，您可以阅读以下问题：

foldl versus foldr behavior with infinite lists

4) 最后，使用foldr的正确替代：

myTakeWhile'' f xs = foldr (\x rs -> if f x then x:rs else []) [] xs

有了这个，你就可以使用无限列表了：

myTakeWhile' (<10) [1..]

你可以看到它如何制作折叠的不同之处：

Prelude> foldr (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0)))))))))))))"

Prelude> foldl (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(((((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)"

本文来自https://wiki.haskell.org/Fold

如何使用 foldl 编写 takeWhile？

How do I write takeWhile using foldl?

haskell

list

fold