Понимание вложенного списка на Haskell - PullRequest
Новая
       18

Понимание вложенного списка на Haskell

1 голос
/ 29 марта 2019

Я готовлюсь к экзамену, и я смотрю на пример понимания вложенного списка из книги «Учим Хаскелла», и я надеялся, что кто-нибудь сможет объяснить мне шаг за шагом, как его анализировать и получить его вывод. 

let xxs = [[1,2,3],[2,3,4],[4,5]]

[ [ x | x <- xs, even x] | xs <- xxs ]]

Выход: ([[2],[2,4],[4]])

Ответы [ 2 ]

2 голосов
/ 29 марта 2019 
[ [ x | x <- xs, even x] | xs <- xxs ]
[ [ x | x <- xs, even x] | xs <- [[1,2,3],[2,3,4],[4,5]] ]
[ [ x | x <- [1,2,3], even x] , [ x | x <- [2,3,4], even x] , [ x | x <- [4,5], even x] ]
[filter even [1,2,3], filter even [2,3,4], filter even [4,5]]
[[2],[2,4],[4]]

Или 

[ [ x | x <- xs, even x] | xs <- xxs ]
map (\xs -> [ x | x <- xs, even x] ) xxs
map (\xs -> filter even xs) [[1,2,3],[2,3,4],[4,5]]
[filter even [1,2,3], filter even [2,3,4], filter even [4,5]]
[[2],[2,4],[4]]

Обратите внимание, что это не преобразование, которое фактически выполняет GHC, а просто способ написания этого, который может помочь вам понять вывод.

1 голос
/ 29 марта 2019

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

[ f x | x <- [],  ... ]       ===   []
[ f x | x <- [y], ... ]       ===   [ f y | {y/x}... ]   -- well, actually, it's
                                    -- case y of x -> [ f y | {y/x}... ] ; _ -> []

[ f x | x <- xs ++ ys, ...]   ===   [ f x | x <- xs, ...] ++ [ f x | x <- ys, ...]

[ f x | True, ...]            ===   [ f x | ... ]
[ f x | False, ...]           ===   []

Обработка сложных шаблонов (в отличие от простых переменных шаблонов) исключается,только намекают, для простоты.{y/x}... означает, y заменено на x в ....Фактическое определение см. В Отчете .

Из этого следует, что 

[ f x | xs <- xss, x <- xs]   ===  concat [ [f x | x <- xs] | xs <- xss]

и 

[ f x | x <- xs, test x ]     ===  map f (filter test xs)

Ваше выражение эквивалентно 

[ [ x | x <- xs, even x] | xs <- xxs ]   -- `]`, sic!
=
[ f xs | xs <- xxs ]  where  f xs = [ x | x <- xs, even x]

То есть, нет ничего особенного в том, что понимание списка используется как выражение значения в определении f.Он выглядит «вложенным», но на самом деле это не так.

Что является вложенным , это выражения генератора, разделенные запятыми: 

[ x | xs <- xss, x <- xs ]   ===   concat [ [x | x <- xs] | xs <- xss ]
--              ^^^ nested generator

(эквивалентностькак мы видели выше.) Итак, 

[ [ x | x <- xs, even x] | xs <- [[1,2,3],[2,3,4],[4,5]] ]
=
[ [ x | x <- [1,2,3], even x]] ++ [[ x | x <- [2,3,4], even x]] ++ [[ x | x <- [4,5], even x] ]
=
[ [ x | x <- [1,2,3], even x], [ x | x <- [2,3,4], even x], [ x | x <- [4,5], even x] ]
=
[ [ x | x <- [1], even x]++[ x | x <- [2], even x]++[ x | x <- [3], even x]
, [ x | x <- [2], even x]++[ x | x <- [3], even x]++[ x | x <- [4], even x]
, [ x | x <- [4], even x]++[ x | x <- [5], even x] ]
=
[ [ 1 | even 1]++[ 2 | even 2]++[ 3 | even 3]
, [ 2 | even 2]++[ 3 | even 3]++[ 4 | even 4]
, [ 4 | even 4]++[ 5 | even 5] ]
=
[ []++[ 2 ]++[], [ 2 ]++[]++[ 4 ], [ 4 ]++[] ]
=
[ [2], [2,4], [4] ]

Или с filter, если хотите, 

[ [ x | x <- [1,2,3], even x], [ x | x <- [2,3,4], even x], [ x | x <- [4,5], even x] ]
=
[ filter even [1,2,3], filter even [2,3,4], filter even [4,5] ]
=
[ [2], [2,4], [4] ]
...