使用“foldl”实现Haskell的“take”函数

Question

使用. 实现 Haskelltake和drop函数foldl。

关于如何使用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

做不到。

左折叠在无限列表上必然发散，但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很好地、忠实地实现了同态，直到reducer函数的参数顺序为止g，使其能够访问当前元素x和当前列表节点xs（这样xs == (x:t)）以及递归结果r。变形的减速器只能访问x和r。

折叠通常编码变态，但这表明右折叠也可以用来编码变态。这是普遍的方式。我觉得它很漂亮。

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

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

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

如果您确实希望通过左折叠完成它，并且您确实确定列表是有限的，则有两个选择：

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这种方式肯定会（？）更加笨拙。可能是一个很好的练习。