Haskell: Как вернуть список возможных разбиений списка

Question

Я пытаюсь написать функцию с именем 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))) 

кусок кода и Hugs и переводчик моего выбора получает мне это сообщение об ошибке

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

Answer 1

Вы потеряли свои парны. Попробуйте

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

То, что вы эффективно пытаетесь написать, - это простой список zipper. Самый простой способ реализовать это

import Data.List (inits, tails) 

split xs = zip (inits xs) (tails xs) 

Answer 2

Вот альтернативное определение:

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

Правда, это не очень эффективно, но, по крайней мере, это краткое :-)

Другой вариант, что даже меньше, , и, вероятно, более эффективными, используя inits и tails от Data.List:

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

Теперь давайте немного поиграем. Мы можем написать inits и tails как foldr с, где мы используем initsA и tailsA представлять то, что известно как алгебры складок:

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!