Блог

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

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

Это результат:

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

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

Редактировать

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

 [(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)]
  

Понимание списка (фактически, понимание монады) может быть разделено на 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]
  

Очищенный код является:

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

Который может быть переработан в ответ Цуоши Ито.

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

Насколько я знаю, существует еще одна схема перевода, это связано с Wadler.

Это дало бы:

 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.