3

我正在尝试编写一个名为 split 的函数，它接受一个列表并返回一个包含所有不同可能性的对列表来对其进行分区，例如

split [4,3,6] = [([],[4,3,6]),([4],[3,6]),([4,3],[6]),([4,3,6],[])]

现在我写了这个

split :: [a] -> [([a],[a])]
split []     = [([],[])]
split (x:xs) = ([],(x:xs)):(zip (map (x:) (map fst split(xs))) (map snd split(xs)))

一段代码和拥抱以及我选择的解释器让我得到这个

ERROR file:.\split.hs:3 - Type error in application
*** Expression     : map snd split xs
*** Term           : map
*** Type           : (e -> f) -> [e] -> [f]
*** Does not match : a -> b -> c -> d

错误信息。我到底做错了什么？为什么 (map snd split xs) 是
(a-> b -> c -> d) 类型？

4

2 回答 2

10

你放错了括号。尝试

split (x:xs) = ([],(x:xs)):(zip (map (x:) (map fst (split xs))) (map snd (split xs)))

Haskell 不像 C 和 Java 那样使用括号来调用函数。当你写map fst split(xs)这和 一样map fst split xs，即编译器认为你试图map用三个参数调用。因此，您需要将调用括起来，split如下所示：map fst (split xs).

您正在有效地尝试编写的是一个简单的列表拉链。实现它的最简单方法是

import Data.List (inits, tails)

split xs = zip (inits xs) (tails xs)
于 2013-02-20T10:29:36.997 回答
6

这是一个替代定义：

splits :: [a] -> [(a, a)]
splits xs = map (flip splitAt xs) [0 .. length xs]

诚然，它不是很有效，但至少它很简洁:-)

另一个版本更短，可能更高效，使用initsand tailsfrom Data.List：

splits :: [a] -> [(a, a)]
splits xs = zip (inits xs) (tails xs)

现在让我们有一点乐趣。我们可以将initsandtails写成foldrs，我们使用initsAandtailsA来表示所谓的折叠代数：

inits :: [a] -> [[a]]
inits = foldr initsA [[]]

initsA :: a -> [[a]] -> [[a]]
initsA x xss = [] : map (x:) xss

tails :: [a] -> [[a]]
tails = foldr tailsA [[]]

tailsA :: a -> [[a]] -> [[a]]
tailsA x xss = (x : head xss) : xss

使用这些代数，我们可以进一步组合它们：

splits :: [a] -> [([a], [a])]
splits = foldr splitsA [([], [])]

splitsA :: a -> [([a], [a])] -> [([a], [a])]
splitsA xy xyss = zip (initsA xy xss) (tailsA xy yss)
  where (xss, yss) = unzip xyss

所以现在我们已经splits定义为单foldr！

于 2013-02-20T10:33:19.750 回答