Haskell от списка пар до пары списков

Question

Я хочу создать простую (с участием наборов и списков) функцию, которая может сделать следующее, и я не уверен, с чего начать.

split:: [(a,b)] -> ([a],[b]) 

Answer 1

Давайте сделаем это шаг за шагом. Два случая для этой функции:

split [] = ??? 
split ((a,b):ps) = ??? 

Один случай легко.

split [] = ([], []) 

Для другого, мы должны использовать функцию рекурсивно, некоторым образом

split ((a,b):ps) = ???? where 
        (as, bs) = split ps 

Я думаю, что это легко видеть, что решение

split ((a,b):ps) = (a:as, b:bs) where 
        (as, bs) = split ps 

Answer 2

В дополнение к решению Гвидо , существует более одного способа сделать это в haskell.

Пожалуйста, взгляните на fst и snd, который берет первый/второй элемент из пары соответственно.

GHCi> :t fst 
fst :: (a, b) -> a 
GHCi> :t snd 
snd :: (a, b) -> b 

Вы должны быть знакомы с map, если вы играете с функциональными языками программирования, который принимает функцию и список, применяет функцию на каждом элементе этого списка, и дает вам все результаты в другом списке:

GHCi> :t map 
map :: (a -> b) -> [a] -> [b] 

Учитывая список пар, вы хотите, два списка, один содержит все первые элементы в порядке, а другой содержит все вторые элементы:

GHCi> let split xs = (map fst xs, map snd xs) 
GHCi> split [(1,2),(3,4),(5,6)] 
([1,3,5],[2,4,6]) 
GHCi> 

Еще один шаг, так как @jozefg указал в комментарии, что этот метод неэффективен, как и @Guido, но мы можем внести некоторые изменения для его улучшения (что и является решением @Guido):

Теперь пришло время взглянуть на то, как map реализуется here

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

так что мы можем попытаться изменить наше split немного:

нам еще базовый вариант (т.е. что, если xs пуста):

split [] = ([], []) 
split ls = (map fst ls, map snd ls) -- attention! 

и мы нарушаем список в голову и хвост, как map:

split (x:xs) = (fst x: map fst xs, snd x: map snd xs) 

Теперь мы можем сделать поиск по шаблону, (a,b) = x, поэтому мы не делаем должны вызвать две отдельные функции, чтобы разбить пару на два:

split (x:xs) = (a: map fst xs, b: map snd xs) 
    where (a,b) = x 

Сравните код здесь с линией я заметил! «внимание», ты понял, что если со я знаю результат (map fst xs, map snd xs), мы можем просто повторно использовать этот результат для ускорения. К счастью, у нас уже есть split ls = (map fst ls, map snd ls)!

Используя этот факт, мы, наконец, придумали эту версию:

split [] = ([], []) 
split (x:xs) = (a:as , b:bs) 
    where (a,b) = x 
      (as,bs) = split xs 

Таким образом, есть по существу то же самое! (но, как видите, последняя версия у нас более эффективна.)