Удаление синтаксического сахара: понимание списка в Haskell

Question

Могу ли я отменить понимание списка в этом выражении:

[(i,j) | i <- [1..4], j <- [i+1..4]]

Это вывод:

[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]

Как я могу, с картой, фильтром и так далее, написать этот кусоккода?

edit

Здесь другое:

[(i,j,k) | i <- [1..6], j <- [i+1..6],k <- [j+1..6]]

Это вывод:

[(1,2,3),(1,2,4),(1,2,5),(1,2,6),(1,3,4),(1,3,5),(1,3,6),(1,4,5),(1,4,6),(1,5,6),(2,3,4),(2,3,5),(2,3,6),(2,4,5),(2,4,6),(2,5,6),(3,4,5),(3,4,6),(3,5,6),(4,5,6)]

Answer 1

Понимания списка (на самом деле, понимания монады) могут быть выведены в нотацию do.

do i <- [1..4]
   j <- [i+1..4]
   return (i,j)

Который можно отключить как обычно:

[1..4]   >>= \i ->
[i+1..4] >>= \j ->
return (i,j)

Хорошо известно, что a >>= \x -> return b совпадает с fmap (\x -> b) a. Итак, промежуточный этап десагеринга:

[1..4] >>= \i -> 
fmap (\j -> (i,j)) [i+1..4]

Для списков (>>=) = flip concatMap и fmap = map

(flip concatMap) [1..4] (\i -> map (\j -> (i,j) [i+1..4])

flip просто переключает порядок входов.

concatMap (\i -> map (\j -> (i,j)) [i+1..4]) [1..4]

И вот как вы получите ответ Цуёси.

---

Второй также может быть выведен в:

concatMap (\i ->
  concatMap (\j ->
    map       (\k ->
      (i,j,k))
    [j+1..6])
  [i+1..6])
[1..6]

Answer 2

Существует еще одна схема перевода, это, насколько я знаю, благодаря Вадлеру.

Это даст:

let
    lc_outer (x:xs) = let lc_inner (y:ys) = (x,y) : lc_inner ys
                          lc_inner []     = lc_outer xs
                      in lc_inner [x+1.. 4]
    lc_outer [] = []
in  lc_outer [1..4]

Этот перевод позволяет избежать ненужного построения списков синглтоновсамый внутренний уровень, который позже потребуется сплющить с помощью concatMap.

Answer 3

Desugared код:

concatMap (\i -> concatMap (\j -> (i, j) : []) [i+1..4]) [1..4]

Что может быть рефакторировано на ответ Цуёси Ито.

Answer 4

concatMap (\i -> map (\j -> (i, j)) [i+1 .. 4]) [1 .. 4]