реализация функции unzip в haskell

Question

Я пытаюсь реализовать функцию unzip, я сделал следующий код, но получаю ошибку.

myUnzip [] =() 
myUnzip ((a,b):xs) = a:fst (myUnzip xs) b:snd (myUnzip xs) 

Я знаю, что проблема находится в правой части второй линии, но я знаю, как ее улучшить. какой-либо подсказка пожалуйста.

ошибка, что я получаю

ex1.hs:190:22: 
Couldn't match expected type `()' with actual type `[a0]' 
In the expression: a : fst (myUnzip xs) b : snd (myUnzip xs) 
In an equation for `myUnzip': 
    myUnzip ((a, b) : xs) = a : fst (myUnzip xs) b : snd (myUnzip xs) 


ex1.hs:190:29: 
Couldn't match expected type `(t0 -> a0, b0)' with actual type `()' 
In the return type of a call of `myUnzip' 
In the first argument of `fst', namely `(myUnzip xs)' 
In the first argument of `(:)', namely `fst (myUnzip xs) b' 

ex1.hs:190:49: 
Couldn't match expected type `(a1, [a0])' with actual type `()' 
In the return type of a call of `myUnzip' 
In the first argument of `snd', namely `(myUnzip xs)' 
In the second argument of `(:)', namely `snd (myUnzip xs)' 

Answer 1

Вы можете сделать это нерационально путем обхода списка дважды

myUnzip [] = ([], []) -- Defaults to a pair of empty lists, not null 
myUnzip xs = (map fst xs, map snd xs) 

Но это не очень идеально, так как он обязан быть довольно медленным по сравнению с только циклом один раз. Чтобы обойти эту проблему, мы должны сделать это рекурсивно

myUnzip [] = ([], []) 
myUnzip ((a, b):xs) = (a : ???, b : ???) 
    where ??? = myUnzip xs 

Я дам вам заполнить пробелы, но это должно быть просто здесь, просто посмотрите на тип подписи myUnzip и выяснить, что вы можете можно положить вместо знаков вопроса на where ??? = myUnzip xs

Answer 2

Вот то, что я получил работу после над наставлениями

myUnzip' [] = ([],[]) 
myUnzip' ((a,b):xs) = (a:(fst rest), b:(snd rest)) 
    where rest = myUnzip' xs 

Answer 3

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

Во-первых, есть прямое решение с использованием складку -

unzip' xs = foldr f x xs 
    where 
    f (a,b) (as,bs) = (a:as, b:bs) 
    x    = ([], []) 

Это использует комбинатор называется foldr для итерации по списку. Вместо этого вы просто определяете функцию объединения f, которая рассказывает вам, как объединить одну пару (a,b) с парой списков (as, bs), и вы определяете начальное значение x.

Во-вторых, помните, что есть миловидная решение

unzip'' xs = (map fst xs, map snd xs) 

который выглядит аккуратно, но выполняет две итерации входного списка. Было бы неплохо написать что-то столь же простое, как это, но которое только итерационно выполняется через список ввода один раз.

Мы можем почти достичь этого, используя библиотеку Foldl. Чтобы объяснить, почему это не совсем работает, см. Примечание в конце - возможно, кто-то с большим количеством знаний/времени может объяснить проблему.

Сначала импортируйте библиотеку и определите личность. Возможно, вам придется запустить cabal install foldl, чтобы установить библиотеку.

import Control.Applicative 
import Control.Foldl 

ident = Fold (\as a -> a:as) [] reverse 

Затем можно определить складки, которые извлекают первый и второй компоненты списка пар,

fsts = map fst <$> ident 
snds = map snd <$> ident 

И, наконец, вы можете объединить эти две складки в один раз, что расстегивает список

unzip' = (,) <$> fsts <*> snds 

Причина, по которой это не совсем работает, состоит в том, что, хотя вы только проходите список один раз, чтобы извлечь пары, они будут извлечены в обратном порядке. Это требует дополнительного вызова reverse в определении ident, что приводит к дополнительному обходу списка, чтобы привести его в правильном порядке. Мне было бы интересно узнать, как это исправить (я ожидаю, что это невозможно с текущей библиотекой Foldl, но может быть возможно с аналогичной библиотекой Foldr, которая отказывается от потоковой передачи, чтобы сохранить порядок входов).

---

Обратите внимание, что ни одна из них не работает с бесконечными списками. Решение, использующее Foldl, никогда не сможет обрабатывать бесконечные списки, потому что вы не можете наблюдать значение левой складки, пока список не завершится.

Однако версия, использующая правую складку , должна работы - но на данный момент не достаточно ленив. В определении

unzip' xs = foldr f x xs 
    where 
    f (a,b) (as,bs) = (a:as, b:bs) -- problem is in this line! 
    x    = ([], []) 

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

unzip'' xs = foldr f x xs 
    where 
    f (a,b) ~(as,bs) = (a:as, b:bs) 
    x    = ([], []) 

так что мы можем теперь сделать

>> let xs = repeat (1,2) 
>> take 10 . fst . unzip' $ xs 
^CInterrupted 
<< take 10 . fst . unzip'' $ xs 
[1,1,1,1,1,1,1,1,1,1] 

Answer 4

Вот Chris Taylor's answer написана с использованием (несколько новых) «сворачивает» пакет:

import Data.Fold (R(R), run) 
import Control.Applicative ((<$>), (<*>)) 

ident :: R a [a] 
ident = R id (:) [] 

fsts :: R (a, b) [a] 
fsts = map fst <$> ident 

snds :: R (a, b) [b] 
snds = map snd <$> ident 

unzip' :: R (a, b) ([a], [b]) 
unzip' = (,) <$> fsts <*> snds 

test :: ([Int], [Int]) 
test = run [(1,2), (3,4), (5,6)] unzip' 

*Main> test 
([1,3,5],[2,4,6])