list - 如何使用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'，另外，折叠还有另一种类型:

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

where 子句的步骤函数中的类型错误就是因为它。

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