Как `[(x !! 0, x !! 1) | x <- mapM (const ['A', 'B', 'C']) [1..2], голова x <голова (хвост x)] `работа?

Question

Я новичок в Haskell и удивляюсь, как работает утверждение

[ (x !! 0, x !! 1) | x <- mapM (const ['A', 'B', 'C'] ) [1..2], head x < head (tail x) ]

. (Я нашел это в StackOverflow.) Я знаю, что он выводит, но я не совсем понимаю.

Answer 1

Ну, вышеприведенное выражение, вероятно, не то, что считается идиоматизм c Haskell. Вероятно, лучшей версией будет:

[ <b>(x0, x1)</b> | <b>(x0:x1:_)</b> <- mapM (const "ABC") [1..2], <b>x0 < x1</b> ]

Это чище, и если списки в mapM (const "ABC") вернут список, который содержит менее двух элементов (что здесь невозможно), это не приведет к ошибке.

Вероятно, основная проблема здесь заключается в том, чтобы понять, как работает mapM. Выражение mapM (const "ABC") [1..2] сводится к:

mapM (\_ -> "ABC") [1..2]

, поскольку мы не учитываем значения списка, оно эквивалентно:

replicateM 2 "ABC"

Это replicateM для 2 может быть переписан как (псевдо-Haskell синтаксис):

replicateM 2 :: [a] -< [[a]]
replicateM 2 l = do
    x0 <- l
    x1 <- l
    return [x0, x1]

или, если мы обнуляем это:

replicateM 2 l = l >>= \x0 -> l >>= \x1 -> return [x0, x1]

Для списка, экземпляр Monad реализован как:

instance Monad [] where
    return x = [x]
    (>>=) = flip concatMap

, что означает, что для списка это replicateM 2, реализовано как:

replicateM 2 l :: [a] -> [[a]]
replicateM 2 l = concatMap (\x0 -> concatMap (\x1 -> [[x0, x1]]) l) l

или проще:

replicateM 2 l :: [a] -> [[a]]
replicateM 2 l = concatMap (\x0 -> map (\x1 -> [x0, x1]) l) l

таким образом мы делаем все возможные комбинации двух пунктов списка. Таким образом, это означает, что:

Prelude Control.Monad> replicateM 2 "ABC"
["AA","AB","AC","BA","BB","BC","CA","CB","CC"]

Затем мы используем это в понимании списка, и для каждого из этих подсписков с двумя элементами мы проверяем, меньше ли первый элемент x0, чем второй элемент с часть фильтра в понимании списка (x0 < x1). Если это так, мы выдаем эти элементы как 2-кортеж.

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

Здесь мы, однако, делаем немного «слишком много работы»: более половины элементов будут отклонены. Мы можем оптимизировать это, используя tails :: [a] -> [[a]]:

import Data.List(tails)

[(x0, x1) | (x0:<b>xs</b>) <- <b>tails "ABC"</b>, x1 <- <b>xs</b> ]

, что дает то же значение:

Prelude Control.Monad Data.List> [(x0, x1) | (x0:xs) <- tails "ABC", x1 <- xs ]
[('A','B'),('A','C'),('B','C')]

Answer 2

Игнорируя вопрос о том, как работает оригинальный код, и сразу переходя к тому, как написать это более идиоматически, начните с myList = ['A', 'B', 'C'].

. Вы можете получить список все возможные пары; выберите x, выберите y и поместите их в кортеж:

> [ (x, y) | x <- myList, y <- myList ]
[('A','A'),('A','B'),('A','C'),('B','A'),('B','B'),('B','C'),('C','A'),('C','B'),('C','C')]

Но вам нужны только те, где x < y:

> [ (x, y) | x <- myList, y <- myList<b>, x < y</b> ]
[('A','B'),('A','C'),('B','C')]

Answer 3

Переписав его согласно определению mapM f xs = sequence (map f xs), мы получим

[ (x !! 0, x !! 1) | x <- mapM (const ['A', 'B', 'C'] ) [1..2], head x < head (tail x) ]
=
[ (a, b) | [a,b] <- mapM (const "ABC" ) [1,2], a < b ]
=
[ (a, b) | [a,b] <- sequence ["ABC" | _ <- [1,2]], a < b ]
=
[ (a, b) | [a,b] <- sequence ["ABC", "ABC"], a < b ]
=
[ (a, b) | [a,b] <- [[a,b] | a <- "ABC", b <- "ABC"], a < b ]   -- by def of sequence
=
[ (a, b) | a <- "ABC", b <- "ABC", a < b ]                 -- by associativity of (++)
=
[ (a, b) | a <- "ABC", b <- [b | b <- "ABC", b > a] ]      -- by associativity of (++)
=
[ (a, b) | a <- "A", b <- [b | b <- "ABC", b > a] ]
   ++
   [ (a, b) | a <- "B", b <- [b | b <- "ABC", b > a] ]
     ++
     [ (a, b) | a <- "C", b <- [b | b <- "ABC", b > a] ]
=
[ (a, b) | a <- "A", b <- [b | b <- "BC"] ]                -- by pre-evaluation
   ++
   [ (a, b) | a <- "B", b <- [b | b <- "C"] ]
     ++
     [ ]
=
[ (a, b) | a <- "A", b <- "BC" ]
   ++
   [ (a, b) | a <- "B", b <- "C" ]
=
[ (a, b) | (a:bs) <- ["ABC", "BC"], b <- bs ]

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

Monadi c do запись тоже забавна и может быть написана как Monad Compreatsions, что для списков выглядит и точно так же как список пониманий.