Почему бесконечные списки не закрывают в Хаскелле?

Я изучаю Хаскелл. Я хотел бы знать почему:

filter (< 40) $ map (^3) [1..] 

Возврати открытый список, в то время как например:

filter (< 40) $ map (^3) [1..50]  

Возврати закрытый список.

3
задан 10.03.2016, 16:58
2 ответа

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

Функции в вопросе filter и map, которые мы можем определять таким образом:

filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (a:as) = 
  let rest = filter p as in if p a then a : rest else rest

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (a:as) = f a : map f as

Сейчас давайте брать второе выражение:

filter (<40) (map (^3) [1..50])  

  -- Forzamos la evaluación de la cabeza de `[1..50]` para 
  -- saber cuál ecuación de `map` debemos usar
  = filter (<40) (map (^3) (1:[2..50]))

  -- Segunda ecuación de `map`:
  = filter (<40) (1^3 : map (^3) [2..50])

  -- Segunda ecuación de `filter`:
  = let rest = filter (<40) (map (^3) [2..50])
    in if 1^3 < 40 then 1^3 : rest else rest

  -- Forzamos la evaluación de `1^3` para poder comparar el 
  -- resultado con `40`:
  = let rest = filter (<40) (map (^3) [2..50])
    in if 1 < 40 then 1 : rest else rest

  = let rest = filter (<40) (map (^3) [2..50])
    in if True then 1 : rest else rest

  -- `if True then x else y = x`, por lo tanto:
  = 1 : filter (<40) (map (^3) [2..50])

  .
  .
  .

  -- Cuando llegamos al final de la lista nos topamos con `[]`:
  = 1 : ... : filter (<40) (map (^3) [])

  -- Primera ecuación de `map`:
  = 1 : ... : filter (<40) []

  -- Primera ecuación de `filter`:
  = 1 : ... : []

То, что нужно закреплять здесь, состоит в том, что эта оценка списком результата "закрывается", когда достигают строителя [] что "закрывает" список [1..50]. В случае [1..] нет такого строителя []. И если мы сосредотачиваемся на определениях filter и map, это означает, что:

  1. Первые уравнения соответствующих определений никогда не входят в игру, когда мы замещаем бесконечный список;
  2. Эти первые уравнения - единственные, что производят один [] что "закрывает" результат;
  3. Следовательно, filter и map, примененные к бесконечным спискам, всегда они производят такие бесконечные списки как результат.
0
ответ дан 24.11.2019, 14:45
  • 1
    Очень хороший explicaci и # 243; n, спасибо. – Ricardo Avila Legrá 22.03.2016, 12:05

Ты выдаешь все элементы бесконечного списка, вышеупомянутого фильтра, который не обладает никакой внутренней структурой (дерево, распорядок, и т.д....) и он применяется к себе ко всем элементам списка.

Бесконечный список как

[1..]

это ленивая последовательность, в которой элементы только оцениваются, когда их потребовали, например, сделав (в интерактивном)

> let xs = [1..]
> print 2
2

он определился xs но никогда он не ссылается на нее, из-за которого ни один из бесконечных элементов xsон был должен быть оцененным.

Если мы делаем

> let xs = [1..]
> print (xs!!3)
2

тогда были должны быть оцененными элементы [0, 1, 2 чтобы прибывать в индекс 2 попросивший.

Как он действует filter?

Функция filter у него есть следующая подпись

filter :: (a -> Bool) -> [a] -> [a]

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

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

Например, результат следующего выражения мы знаем, что это пустой список

filter (const False) [1..]

но мы просим у него подтверждать вышеупомянутую функцию на бесконечных элементах списка!

Обоснованные альтернативы в твой код были бы

take 10 $ filter odd $ map (^3) [1..]
take 10 $ filter even $ map (^3) [1..]
takeWhile (<40) $ map (^3) [1..]
take 10 $ dropWhile (<40) $ map (^3) [1..]

и т.д....

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

5
ответ дан 24.11.2019, 14:45
  • 1
    Привет, альтернативы, которые он предлагает, не дают те же результаты. Я остаюсь, не понимая. Спасибо так или иначе. – Ricardo Avila Legrá 11.03.2016, 11:03
  • 2
    @RicardoAvilaLegr и # 225; и #191; не дают те же результаты, что qu и # 233; вещь, которая требуется?, они s и # 243; примеры. Я увеличил explicaci и # 243; n, я надеюсь, что остается м и # 225; s просвет. – josejuan 11.03.2016, 11:30
  • 3
    Я это понял сейчас: – Ricardo Avila Legrá 13.03.2016, 18:07
  • 4
    Я думаю, что вещь идет, схвати и # 237;: filter (< 40) $ map (^3) [1.] не работает, потому что, хотя говорится о конечном списке для нас, для haskell - бесконечный список, так как он должен подтверждать все элементы бесконечного списка. Окончательный список строится, как ушла requierendo стоимость из-за какой-то другой функции, которая просила бы их (давайте говорить takeWhile). Большое спасибо. – Ricardo Avila Legrá 13.03.2016, 18:12