Haskell: разделение списка на два новых списка

Question

Мне трудно понять, как разбить список 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))    

Answer 1

Ваша функция split возвращает пару, но в последнем случае вы используете ++ для результата split. Это будет ошибка типа, поскольку ++ работает со списками, а не с парами. Существует также ошибка типа, потому что 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

Answer 2

Другой способ сделать это - с помощью взаимной рекурсии. Очень легко читается:

split xs = (odds xs, evens xs)

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

evens xs = odds (drop 1 xs)

Answer 3

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)) ([], [])

Answer 4

Haskell Blow Your Mind wiki, имеет несколько лайнеров:

-- 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))

Answer 5

Две альтернативные версии:

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..]

Answer 6

Если вы ищете альтернативный способ сделать это, ниже приведена одна из таких реализаций:

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

Answer 7

В последнем предложении есть ошибка. Вы должны получить результаты рекурсивного вызова, а затем добавить к ним первый и второй элементы.

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)