哈斯克尔：拆分列表为两个新的列表

我有困难搞清楚如何INTS的名单分成包含两个新的列表，元组的元组，使得每一个元素（从第一个）进入第一个列表，每其他元素在第二。哈斯克尔：拆分列表为两个新的列表

像这样：

split [] = ([],[]) 
split [1] = ([1],[]) 
split [1,2] = ([1],[2]) 
split [1,2,3] = ([1,3],[2]) 
split [1,2,3,4] = ([1,3],[2,4])

我试图递归地做到这一点（有警卫），并且仅使用单个参数XS

这是我的方法，保持收到错误消息：

split :: [Int] -> ([Int],[Int]) 
split xs | length(xs) == 0 = ([],[]) 
     | length(xs) == 1 = (xs !! 0 : [],[]) 
     | length(xs) == 2 = (xs !! 0 : [], xs !! 1 : []) 
     | otherwise = (fst ++ xs !! 0, snd ++ xs !! 1) ++ split(drop 2 xs))

来源

2011-09-14 Shabu

谢谢你们！ – Shabu

你应该接受其中一个答案。 –

您的split函数返回一对，但在最后一种情况下，您对的结果使用++ 0。这将是一个类型错误，因为++适用于列表，而不是对。还有一个类型错误，因为fst和snd是挑选一对元素的函数，但是使用它们是一种奇怪的方法。

此外，使用模式匹配而不是使用长度。此外，您不需要测试长度是2的情况，因为一般情况下会删除2个元素，这会将您带到空列表的基本情况。

您也可以让你的功能更普遍的可变a，而不是Int在类型中使用的类型。

[编辑]：添加代码

split :: [a] -> ([a], [a]) 
split [] = ([], []) 
split [x] = ([x], []) 
split (x:y:xys) = (x:xs, y:ys) where (xs, ys) = split xys

来源

2011-09-14 03:46:00 augustss

另外'分裂（Z：ZS）=（Z：YS，XS），其中（XS，YS）=分裂zs'！ – Zantier

还有最后一句话，在一个错误。您必须从递归调用中获得结果，然后向它们添加第一个和第二个元素。

split :: [Int] -> ([Int],[Int]) 
split xs | length(xs) == 0 = ([],[]) 
     | length(xs) == 1 = (xs !! 0 : [],[]) 
     | length(xs) == 2 = (xs !! 0 : [], xs !! 1 : []) 
     | otherwise = let (fst, snd) = split(drop 2 xs) in 
        (xs !! 0 : fst, xs !! 1 : snd)

来源

2011-09-14 03:50:34 bravit

这仍然是写这个函数的一个可怕的方法。 – augustss

是的，你是绝对正确的。但我试图按照问题“递归地做到这一点（有警卫），并且仅使用单个参数XS” – bravit

你仍然可以做到这一点，并得到O（n）的复杂性，而不是为O（n^2）。 – augustss

split :: [a] -> ([a], [a]) 
split xs | null xs = ([], []) 
     | otherwise = (head xs : snd pair, fst pair) 
    where pair = split (tail xs)

但是，你应该使用折叠：

split :: [a] -> ([a], [a]) 
split = foldr (\x (ys, zs) -> (x : zs, ys)) ([], [])

来源

2011-09-14 06:16:23 dave4420

这段代码并没有做他所要求的，它也不好，因为它使用'head'和'tail'代替模式匹配。 – augustss

请给我一个输入的例子，我的代码给出了错误的结果。（你指的是递归和守卫版本还是foldr版本？）我同意模式匹配会比'head'和'tail'好，但是OP似乎想要使用守卫--- **在这种情况下** ---排除了模式匹配（在模式匹配之后没有任何事情可以留待）。 – dave4420

对不起，我收回它是错误的。没有足够的咖啡。 :) – augustss

在你正在寻找一些替代的方式来做到这一点的情况下，下面是一个这样的实现方式：

split xs = 
    let (a,b) = partition (odd . snd) (zip xs [1..]) 
    in ((map fst a), (map fst b))

来源

2011-09-14 06:37:47 Ankur

两种替代版本：

split = conv . map (map snd) . groupWith (even.fst) . zip [0..] where 
    conv [xs,ys] = (xs,ys) 

split xs = (ti even xs, ti odd xs) where 
    ti f = map snd . filter (f.fst) . zip [0..]

来源

2011-09-14 07:23:57 Landei

另一种方式做，这是相互递归。它配备了非常容易阅读：

split xs = (odds xs, evens xs) 

odds (x:xs) = x : evens xs 
odds xs  = [] 

evens xs = odds (drop 1 xs)

来源

2011-09-14 15:20:19 Yitz

哈斯克尔Blow Your Mind维基，有一些一个衬垫：

-- splitting in two (alternating) 
-- "1234567" -> ("1357", "246") 

-- the lazy match with ~ is necessary for efficiency, especially enabling 
-- processing of infinite lists 
foldr (\a ~(x,y) -> (a:y,x)) ([],[]) 

(map snd *** map snd) . partition (even . fst) . zip [0..] 

transpose . unfoldr (\a -> toMaybe (null a) (splitAt 2 a))

来源

2012-06-07 20:35:19

哈斯克尔：拆分列表为两个新的列表

回答

相关问题