Haskell - два списка в список кортежей

Это отличное упражнение!

Если мы выложим пары вашего ввода в бесконечную таблицу:

(0,A)  (1,A)  (2,A)  (3,A) ...
(0,B)  (1,B)  (2,B)  (3,B) ...
(0,C)  (1,C)  (2,C)  (3,C) ...
(0,D)  (1,D)  (2,D)  (3,D) ...
...

Хитрость заключается в том, чтобы пересечь стол диагональными полосами вверх. Обведите стол глазами. Полосы этой таблицы:

(0,A)
(0,B) (1,A)
(0,C) (1,B) (2,A)
(0,D) (1,C) (2,B) (3,A)
...

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

Вот план игры, который я бы предложил:

Реализуйте stripes :: [[a]] -> [[a]], который извлекает список полос из бесконечного массива, как указано выше (начните с предположения, что все списки бесконечны, то есть не беспокойтесь о [] случаях; как только у вас это заработает, исправьте его, чтобы работать со списками, которые могут быть конечными ).

Используя stripes, реализуйте diagonal :: [[a]] -> [a], который объединяет все полосы (это однострочный).

Наконец, реализуйте свою функцию, применив diagonal конкретной 2D-таблицы [[(a,b)]], которая является таблицей, с которой я начал этот ответ (и может быть построена с использованием понимания вложенного списка, среди других различных способов).

Примечания:

• Название zip вводит в заблуждение. Это больше похоже на декартово произведение.

• Вы знаете, что вы можете сопоставить шаблоны внутри шаблонов, верно? Т.е. если f :: [[a]] -> something

  f ((x:xs):xss) = ...
  

  Дает вам x в качестве первого элемента первой строки, xs - оставшуюся часть первой строки, а xss - оставшуюся часть таблицы.

Хотя это отличное упражнение для понимания списков и Haskell в целом, это также отличное упражнение для понимания того, что такое класс Applicative. В частности, экземпляр [] для Applicative. Ваш zipInf, который вам нужен, ровно liftA2 (,)

λ: :t liftA2
liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
λ: :t (,)
(,) :: a -> b -> (a, b)
λ: :t liftA2 (,)
liftA2 (,) :: Applicative f => f a -> f b -> f (a, b)

Нам просто нужно убедиться, что [] - это Applicative.

λ: :i []
...
instance Applicative [] -- Defined in `Control.Applicative'
...

Так что это Applicative. Это может упростить понимание, если мы немного аннотируем наш тип

λ: :t liftA2 (,) `asAppliedTo` []
[a] -> [b] -> [(a, b)]

Ага, это того же типа.

λ: liftA2 (,) [0..2] ['A'..'C']
[(0,'A'),(0,'B'),(0,'C'),(1,'A'),(1,'B'),(1,'C'),(2,'A'),(2,'B'),(2,'C')]

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

Вы также можете написать его немного более идиоматично, используя <$> (или fmap) и <*>.

λ: (,) <$> [0..2] <*> ['A'..'C']
[(0,'A'),(0,'B'),(0,'C'),(1,'A'),(1,'B'),(1,'C'),(2,'A'),(2,'B'),(2,'C')]
λ: take 9 $ (,) <$> "A" <*> [0..]
[('A',0),('A',1),('A',2),('A',3),('A',4),('A',5),('A',6),('A',7),('A',8)]

Или вы можете использовать всю мощь Monad (что в данном случае совершенно не нужно):

λ: do {n <- [0..2]; c <- ['A'..'C']; return (n, c)}
[(0,'A'),(0,'B'),(0,'C'),(1,'A'),(1,'B'),(1,'C'),(2,'A'),(2,'B'),(2,'C')]

Кроме того, если вам интересно, как можно получить другую семантику от Applicative для [], существует хотя бы один другой экземпляр списка для Applicative: ZipList

λ: :i ZipList
newtype ZipList a = ZipList {getZipList :: [a]}
    -- Defined in `Control.Applicative'
instance Functor ZipList -- Defined in `Control.Applicative'
instance Applicative ZipList -- Defined in `Control.Applicative'

Этот экземпляр предоставляет семантику стиля сжатия для своего экземпляра Applicative.

λ: getZipList $ (,) <$> ZipList [0..2] <*> ZipList ['A'..'C']
[(0,'A'),(1,'B'),(2,'C')]

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

Вот опубликованная вами вспомогательная функция:

oneList :: [a] -> [b] [(a,b)]
oneList [] _ = []
oneList x:xs y:ys = [(x,y)] ++ oneList

И вот синтаксические ошибки, которые он содержит:

• вы не указали стрелку в аннотации типа; должен быть

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

• вам нужно заключить нетривиальные шаблоны в скобки, поэтому второе уравнение должно начинаться

  oneList (x:xs) (y:ys) =
  

• oneList принимает два аргумента перед тем, как вернуть список, но в правой части второго уравнения вы пытаетесь использовать его как список без каких-либо аргументов.

(Кстати, нам обычно помогает, если вы публикуете сообщения об ошибках, а не просто говорите, что он не компилируется. Сравните ошибки, которые я указал выше, с сообщениями об ошибках, которые вам дал компилятор.)

Но, как вы заметили, ваш алгоритм неверен.

Я чувствую, что это домашнее задание, поэтому дам вам только намек.

zipInf должно быть

zipInf :: [a] -> [b] -> [(a,b)]
zipInf xs ys = thread (expand xs ys)

thread и expand - две вспомогательные функции, которые я оставляю вам писать, с подписями типов

expand :: [a] -> [b] -> [[(a,b)]]
thread :: [[c]] -> [c]

expand довольно просто. thread - это то место, где вы должны быть осторожны, чтобы включать элементы в правильном порядке (следовательно, вы не можете просто сказать thread zs = concat zs, даже если тип правильный).

Вам нужно применить oneList к xs и ys.

oneList :: [a] -> [b] -> [(a, b)]
oneList []     _      = []
oneList (x:xs) (y:ys) = (x, y) : oneList xs ys

Бесконечные списки будут работать автоматически, поскольку Haskell ленив.

ВАЖНО: См. комментарий Уилла Несса ниже.

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

λ> let xs = "abcdef"
λ> let ys = "ABCDEFGHI"
λ> [(x,y) | x <- xs, y <- ys]
[('a','A'),('a','B'),('a','C'),('a','D'),('a','E'),('a','F'),('a','G'),('a','H'),('a','I'),('b','A'),('b','B'),('b','C'),('b','D'),('b','E'),('b','F'),('b','G'),('b','H'),('b','I'),('c','A'),('c','B'),('c','C'),('c','D'),('c','E'),('c','F'),('c','G'),('c','H'),('c','I'),('d','A'),('d','B'),('d','C'),('d','D'),('d','E'),('d','F'),('d','G'),('d','H'),('d','I'),('e','A'),('e','B'),('e','C'),('e','D'),('e','E'),('e','F'),('e','G'),('e','H'),('e','I'),('f','A'),('f','B'),('f','C'),('f','D'),('f','E'),('f','F'),('f','G'),('f','H'),('f','I')]

Обратите внимание, что сначала печатаются все кортежи с 'a', затем с 'b' и так далее. Почему это имеет значение? Предположим, список бесконечен. Такой запрос вернется мгновенно:

(1,'a') `elem` [(x,y) | x <- [1..], y <- ['a'..]]

Но один такой займёт ДОЛГОЕ ВРЕМЯ:

(200000,'a') `elem` [(x,y) | x <- [1..], y <- ['a'..]]

Если порядок имеет значение, или вы не сталкивались с пониманием списков, или не хотите их использовать, подход luqui, вероятно, то, что вы ищете.

Вы можете сделать это очень просто, используя понимание списка.

zip :: [a] -> [b] -> [(a,b)]
zip [] _ = [] 
zip _ [] = []
zip as bs = [(a, b) | a <- as, b <- bs]

Он отлично работает как с конечными, так и с бесконечными списками. Конечно, вы хотите, чтобы хотя бы одна из них была конечной, или она должна состоять только из всех комбинаций head as и bs.

> zip [0..2] ['A'..'C']
[(0,'A'),(0,'B'),(0,'C'),(1,'A'),(1,'B'),(1,'C'),(2,'A'),(2,'B'),(2,'C')]

> take 50 $ zip [0..] ['A'..'C']
[(0,'A'),(0,'B'),(0,'C'),(1,'A'),(1,'B'),(1,'C'),(2,'A'),(2,'B'),(2,'C'),(3,'A'),(3,'B'),(3,'C'),(4,'A'),(4,'B'),(4,'C'),(5,'A'),(5,'B'),(5,'C'),(6,'A'),(6,'B'),(6,'C'),(7,'A'),(7,'B'),(7,'C'),(8,'A'),(8,'B'),(8,'C'),(9,'A'),(9,'B'),(9,'C'),(10,'A'),(10,'B'),(10,'C'),(11,'A'),(11,'B'),(11,'C'),(12,'A'),(12,'B'),(12,'C'),(13,'A'),(13,'B'),(13,'C'),(14,'A'),(14,'B'),(14,'C'),(15,'A'),(15,'B'),(15,'C'),(16,'A'),(16,'B')]

> take 50 $ zip [0..] [1..]
[(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),(0,10),(0,11),(0,12),(0,13),(0,14),(0,15),(0,16),(0,17),(0,18),(0,19),(0,20),(0,21),(0,22),(0,23),(0,24),(0,25),(0,26),(0,27),(0,28),(0,29),(0,30),(0,31),(0,32),(0,33),(0,34),(0,35),(0,36),(0,37),(0,38),(0,39),(0,40),(0,41),(0,42),(0,43),(0,44),(0,45),(0,46),(0,47),(0,48),(0,49),(0,50)]