使用`foldl`实现Haskell的`take`函数

Question

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

关于如何使用foldl实现take和drop函数，有什么建议吗？

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

Answer 1

不能这样做。

Left fold在无限列表上必然发散，但take n并非如此。这是因为left fold是尾部递归的，所以它必须先扫描整个输入列表，然后才能开始处理。

使用正确的折叠层，它是

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很好地忠实地实现了参数同构，直到reducer函数g的参数顺序，使它能够访问当前元素x和当前列表节点xs (比如xs == (x:t))以及递归结果r。变形的还原器只能访问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必然是(?)甚至更笨拙。可能是个不错的练习。

Answer 2

我注意到您从未指定文件夹必须在提供的列表上。所以，一种符合你问题文字的方法，尽管可能不是精神，是：

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]上--数字本身被忽略，并且列表只是用于它的长度，以便为给定的n构建一个定制的take n或drop n函数。然后将此函数应用于原始提供的列表xs。

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

> sillytake 5 $ sillydrop 5 $ [1..]
[6,7,8,9,10]

Answer 3

Will Ness展示了一种用foldr实现take的好方法。使用foldr实现drop的最不令人讨厌的方法是：

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

接受效率损失，如果你没有选择的话，重新构建整个列表！与其用锤子把螺丝钉进去，不如用螺丝刀把钉子钉进去。

这两种方式都很可怕。但这篇文章可以帮助你理解如何使用折叠来构造函数，以及它们的限制是什么。

Folds不是实现drop的正确工具；准同构才是正确的工具。