1

使用 .实现 Haskell 的take和drop函数foldl。

关于如何使用 实现取放功能的任何建议foldl？

take x ls = foldl ???

drop x ls = foldl ???

我已经尝试过这些，但它显示错误：

myFunc :: Int -> [a] -> [a]
myFunc n list = foldl func [] list
    where 
    func x y | (length y) > n = x : y 
             | otherwise      = y

产生错误：

*** Expression : foldl func [] list
*** Term : func
*** Type : a -> [a] -> [a]
*** Does not match : [a] -> [a] -> [a]
*** Because : unification would give infinite type
4

4 回答 4

4

做不到。

左折叠必然在无限列表上发散，但take n不会。这是因为左折叠是尾递归的，所以它必须扫描整个输入列表才能开始处理。

用正确的折叠，它是

ntake :: Int -> [a] -> [a]
ntake 0 _  = []
ntake n xs = foldr g z xs 0
    where
    g x r i | i>=n      = []
            | otherwise = x : r (i+1)
    z _ = []

ndrop :: Int -> [a] -> [a]
ndrop 0 xs = xs
ndrop n xs = foldr g z xs 0 xs
    where
    g x r i xs@(_:t) | i>=n      = xs
                     | otherwise = r (i+1) t
    z _ _ = []

ndrop很好地忠实地实现了一个paramorphism，直到reducer函数的参数顺序g，使它可以访问当前元素x和当前列表节点xs（例如xs == (x:t)）以及递归结果r。catamorphism的reducer 只能访问x和r。

折叠通常编码变态，但这表明正确的折叠也可以用来编码超态。就是这样通用的。我认为它很漂亮。

至于类型错误，要修复它只需将参数切换到您的func：

       func y x | ..... = .......

左折叠中的累加器作为reducer 函数的第一个参数。

如果你真的想用左折叠完成，并且你真的确定列表是有限的，有两个选择：

ltake n xs = post $ foldl' g (0,id) xs
    where
    g (i,f) x | i < n = (i+1, f . (x:))
              | otherwise = (i,f)
    post (_,f) = f []

rltake n xs = foldl' g id xs r n
    where
    g acc x = acc . f x
    f x r i | i > 0 = x : r (i-1)
            | otherwise = []
    r _ = []

第一个从左往上计数，可能会停止在完整列表遍历中间组装前缀，但它确实携带到最后，是左折叠。

第二个也完全遍历列表，将其转换为右折叠，然后再次从左侧倒计时开始工作，一旦组装前缀就能够真正停止工作。

drop以这种方式实现肯定会（？）更加笨拙。可能是一个很好的锻炼。

于 2019-04-04T19:55:45.403 回答
3

我注意到您从未指定折叠必须超过提供的列表。因此，一种符合您问题字面意思的方法（尽管可能不是精神）是：

sillytake :: Int -> [a] -> [a]
sillytake n xs = foldl go (const []) [1..n] xs
  where go f _ (x:xs) = x : f xs
        go _ _ []     = []

sillydrop :: Int -> [a] -> [a]
sillydrop n xs = foldl go id [1..n] xs
  where go f _ (_:xs) = f xs
        go _ _ []     = []

这些每个都使用左折叠，但在数字列表上[1..n]- 数字本身被忽略，并且列表仅用于其长度来构建给定的自定义take n或drop n函数n。然后将此函数应用于原始提供的列表xs。

这些版本在无限列表上运行良好：

> sillytake 5 $ sillydrop 5 $ [1..]
[6,7,8,9,10]
于 2019-04-09T03:21:54.900 回答
2

Will Ness 展示了一个很好的实现take方式foldr。最不令人厌恶的实现方式drop是foldr：

drop n0 xs0 = foldr go stop xs0 n0
  where
    stop _ = []
    go x r n
      | n <= 0 = x : r 0
      | otherwise = r (n - 1)

如果您别无选择，请承担效率损失并重建整个列表！用螺丝刀打钉子比用锤子打螺丝要好。

两种方式都很可怕。但这可以帮助您了解折叠如何用于构造函数以及它们的限制是什么。

折叠并不是实施的正确工具drop；paramorphism是正确的工具。

于 2019-04-04T23:04:20.997 回答
0

你还不算太远。这是一对修复。

首先，请注意首先func传递累加器（即a，在您的情况下是一个列表），然后是列表元素（an a）。因此，您需要交换 的参数的顺序func。

然后，如果我们想模仿take，我们需要在小于而不是大于x时添加！length yn

所以我们得到

myFunc :: Int -> [a] -> [a]
myFunc n list = foldl func [] list
    where 
    func y x | (length y) < n = x : y 
             | otherwise      = y

测试：

> myFunc 5 [1..10]
[5,4,3,2,1]

如您所见，这是反转字符串。这是因为我们x在前面 ( x:y) 而不是在后面 ( y++[x]) 添加。或者，另一种选择是，可以使用reverse (foldl ....)在最后固定订单。

此外，由于foldl总是扫描整个输入列表，myFunc 3 [1..1000000000]将花费大量时间，并且myFunc 3 [1..]无法终止。使用foldr会好很多。

drop做起来更棘手。我认为如果没有一些后处理myFunc n xs = fst (foldl ...)或foldl返回一个你立即调用的函数（这也是一种后处理），你不能轻易做到这一点。

于 2019-04-04T20:26:09.447 回答