使用 foldr Haskell 反转列表列表

Question

我正在尝试使用 foldr 反转 Haskell 中的列表列表。有一个我想做的例子：

> reverse'' [[1,2,3],[3,4,5]]
[[5,4,3],[3,2,1]]

还有我的代码（不工作）：

reverse'':: [[a]]->[[a]]
reverse'' x = foldr (\n acum -> acum:(foldr(\m acum1 -> acum1++[m])) [] n) [[]] x

我的 IDE 在第二个文件夹的开头报告我一个错误。

Answer 1

为了分析您当前的解决方案，我将您的单行代码分解为一些辅助函数，并根据它们的组成推导出它们的类型：

reverse'':: [[a]] -> [[a]]
reverse'' x = foldr f [[]] x
    where
        f :: [a] -> a -> [a]
        f n acum = acum : reverse n

        reverse :: [a] -> [a]
        reverse n = foldr append [] n

        append :: a -> [a] -> [a]
        append m acum = acum ++ [m]

当我尝试编译上面的代码时，ghc 抱怨 reverse'' 的类型签名出现以下错误：

Expected type: [[a]] -> [[a]] -> [[a]]
  Actual type: [[a]] ->  [a]  -> [[a]]

我做了一些挖掘，为了使 reverse'' 具有类型 [[a]] -> [[a]]，函数 f 需要具有类型 [a] -> [[a]] -> [[a]]。但是当前 f 的类型为 [a] -> a -> [a]，或者在本例中为 [[a]] -> [a] -> [[a]].

以下具有正确的类型，但由于累加器的起始值，将额外的 [] 值插入到数组的开头：

reverse'':: [[a]] -> [[a]]
reverse'' x = foldr f [[]] x
    where
        f :: [a] -> [[a]] -> [[a]]
        f n acum = acum ++ [reverse n]

        reverse :: [a] -> [a]
        reverse n = foldr append [] n

        append :: a -> [a] -> [a]
        append m acum = acum ++ [m]

最终解决方案

通过将初始累加器值更改为空列表 []，而不是空列表的列表 [[]]，我们最终得到一个可行的解决方案：

reverse'':: [[a]] -> [[a]]
reverse'' x = foldr f [] x
    where
        f :: a -> [a] -> [a]
        f n acum = acum ++ [reverse n]

        reverse :: [a] -> [a]
        reverse n = foldr append [] n

        append :: a -> [a] -> [a]
        append m acum = acum ++ [m]

单行

如果你真的想把它作为单行线，这里是：

reverse'' :: [[a]] -> [[a]]
reverse'' = foldr (\n acum -> acum ++ [foldr (\m acum1 -> acum1 ++ [m]) [] n]) []

有工作：

append m acum = acum ++ [m]
append = \m acum1 -> acum1 ++ [m]

reverse n = foldr append [] n
reverse = \n -> foldr append [] n
reverse = foldr append []
reverse = foldr (\m acum1 -> acum1 ++ [m]) []

f n acum = acum ++ [reverse n]
f = \n acum -> acum ++ [reverse n]
f = \n acum -> acum ++ [foldr (\m acum1 -> acum1 ++ [m]) [] n]

reverse'':: [[a]] -> [[a]]
reverse'' x = foldr f [] x
reverse'' x = foldr (\n acum -> acum ++ [foldr (\m acum1 -> acum1 ++ [m]) [] n]) [] x
reverse'' = foldr (\n acum -> acum ++ [foldr (\m acum1 -> acum1 ++ [m]) [] n]) []

附录：显式递归解决方案

这是一个明确的递归解决方案（即不使用 fold），提供了 map 和 reverse 的定义。

reverse :: [a] -> [a]
reverse (x:xs) = reverse xs ++ [x]
reverse []     = []

map :: (a -> b) -> [a] -> [b]
map f (x:xs) = f x : map f xs
map _ [] = []

reverse'' :: [[a]] -> [[a]]
reverse'' ls = reverse $ map reverse ls

使用 foldr Haskell 反转列表列表

Reverse list of lists using foldr Haskell

haskell

list

fold

最终解决方案

单行

附录：显式递归解决方案