Haskell Let Оценка выражений

Question

Я занимаюсь практическими проблемами, которые оценивают выражение let, и я не понимаю, как это получается.

Вот выражение:

let a = 2
    b = 1:[i * 2 | i <- b]
    f a = 1:[i * a | i <- (f a)]
in take (a+2) (f (head (tail b) ))

Выход должен быть [1,2,4,8]. Может кто-нибудь объяснить, пожалуйста, шаг за шагом, почему это вывод

Answer 1

Вот пошаговое объяснение:

let a = 2
    b = 1:[i * 2 | i <- b]
    f a = 1:[i * a | i <- (f a)]
in take (a+2) (f (head (tail b) ))

Там есть две разные переменные, называемые a, и одна затеняет другую, поэтому сначала давайте переименуем одну из них, чтобы случайно не перепутать их:

let outer_a = 2
    b = 1:[i * 2 | i <- b]
    f a = 1:[i * a | i <- (f a)]
in take (outer_a+2) (f (head (tail b) ))

Теперь мы можем подставить outer_a и оценить +:

let b = 1:[i * 2 | i <- b]
    f a = 1:[i * a | i <- (f a)]
in take 4 (f (head (tail b) ))

Перепишите списки в терминах map:

let b = 1:map (* 2) b
    f a = 1:map (* a) (f a)
in take 4 (f (head (tail b) ))

Использовать iterate вместо явной рекурсии:

let b = iterate (* 2) 1
    f a = iterate (* a) 1
in take 4 (f (head (tail b) ))

Оцените первые два шага b:

let b = 1:2:iterate (* 2) 4
    f a = iterate (* a) 1
in take 4 (f (head (tail b) ))

Заменить на b:

let f a = iterate (* a) 1
in take 4 (f (head (tail (1:2:iterate (* 2) 4)) ))

Оценить tail:

let f a = iterate (* a) 1
in take 4 (f (head (2:iterate (* 2) 4) ))

Оценка head:

let f a = iterate (* a) 1
in take 4 (f 2)

Заменить на f a:

take 4 (iterate (* 2) 1)

Оцените iterate несколько раз:

take 4 (1:2:4:8:iterate (* 2) 16)

Оценить take:

[1,2,4,8]

И мы закончили.

Answer 2

Чтобы увидеть, что происходит, мы тщательно назовем каждую сущность так, как она возникла:

let a   = 2
    b   = 1 : [i * 2 | i <- b]
    f a = 1 : [i * a | i <- f a]
in  take (a+2) (f (head (tail b)))
==
let b        = (b1:bs1)
    (b1:bs1) = 1 : [i * 2 | i <- b]
in  take 4 (f (head (tail b)))
==
let b1  = 1
    bs1 = [i * 2 | i <- (b1:bs1)]
in  take 4 (f (head bs1))
==
let b1  = 1
    bs1 = [i * 2 | i <- [b1]] ++ [i * 2 | i <- bs1]
in  take 4 (f (head bs1))
==
let bs1 = [i * 2 | i <- [1]] ++ [i * 2 | i <- bs1]
in  take 4 (f (head bs1))
==
let bs1      = (b2:bs2)
    (b2:bs2) = [1 * 2] ++ [i * 2 | i <- bs1]
in  take 4 (f b2)
==
let (b2:bs2) = 2 : [i * 2 | i <- (b2:bs2)]
in  take 4 (f b2)
==
let bs2      =     [i * 2 | i <- (2:bs2)]
    f a      = 1 : [i * a | i <- f a]     -- same as before
in  take 4 (f 2)
==
let xs       = f 2
    f 2      = 1 : [i * 2 | i <- f 2] 
in  take 4 xs
==
let (x1:xs1) = 1 : [i * 2 | i <- f 2]
in  take 4 (x1:xs1)
==
let xs1      =     [i * 2 | i <- f 2]
in  take 4 (1:xs1)
==
let xs1      =     [i * 2 | i <- f 2]
in  1 : take 3 xs1
==
let (x2:xs2) =     [i * 2 | i <- (y1:ys1)]
    (y1:ys1) = 1 : [i * 2 | i <- f 2]
in  1 : take 3 (x2:xs2)
==
let (x2:xs2) =     [i * 2 | i <- (1:ys1)]
    ys1      =     [i * 2 | i <- f 2]
in  1 : take 3 (x2:xs2)
==
let (x2:xs2) = 2 : [i * 2 | i <- ys1]
    ys1      =     [i * 2 | i <- f 2]
in  1 : take 3 (x2:xs2)
==
let xs2      =     [i * 2 | i <- ys1]
    ys1      =     [i * 2 | i <- f 2]
in  1 : take 3 (2:xs2)
==
let xs2      =     [i * 2 | i <- ys1]
    ys1      =     [i * 2 | i <- f 2]
in  1 : 2 : take 2 xs2
==
let (x3:xs3) =     [i * 2 | i <- (y2:ys2)]
    (y2:ys2) =     [i * 2 | i <- (z1:zs1)]
    (z1:zs1) = 1 : [i * 2 | i <- f 2]
in  1 : 2 : take 2 (x3:xs3)
==
let (x3:xs3) =     [i * 2 | i <- (y2:ys2)]
    (y2:ys2) = 2 : [i * 2 | i <- zs1]
    zs1      =     [i * 2 | i <- f 2]
in  1 : 2 : take 2 (x3:xs3)
==
let (x3:xs3) = 4 : [i * 2 | i <- ys2]
    ys2      =     [i * 2 | i <- zs1]
    zs1      =     [i * 2 | i <- f 2]
in  1 : 2 : take 2 (x3:xs3)
==
let xs3      =     [i * 2 | i <- ys2]
    ys2      =     [i * 2 | i <- zs1]
    zs1      =     [i * 2 | i <- f 2]
in  1 : 2 : 4 : take 1 xs3
==
let (x4:xs4) =     [i * 2 | i <- (y3:ys3)]
    (y3:ys3) =     [i * 2 | i <- (z2:zs2)]
    (z2:zs2) =     [i * 2 | i <- (w1:ws1)]
    (w1:ws1) = 1 : [i * 2 | i <- f 2]
in  1 : 2 : 4 : take 1 (x4:xs4)
==
let (x4:xs4) =     [i * 2 | i <- (y3:ys3)]
    (y3:ys3) =     [i * 2 | i <- (z2:zs2)]
    (z2:zs2) = 2 : [i * 2 | i <- ws1]
    ws1      =     [i * 2 | i <- f 2]
in  1 : 2 : 4 : take 1 (x4:xs4)
==
let (x4:xs4) =     [i * 2 | i <- (y3:ys3)]
    (y3:ys3) = 4 : [i * 2 | i <- zs2]
    zs2      =     [i * 2 | i <- ws1]
    ws1      =     [i * 2 | i <- f 2]
in  1 : 2 : 4 : take 1 (x4:xs4)
==
let (x4:xs4) = 8 : [i * 2 | i <- ys3]
    ys3      =     [i * 2 | i <- zs2]
    zs2      =     [i * 2 | i <- ws1]
    ws1      =     [i * 2 | i <- f 2]
in  1 : 2 : 4 : take 1 (x4:xs4)
==
    1 : 2 : 4 : 8 : take 0 xs4
==
    1 : 2 : 4 : 8 : []

В приведенном выше выводе мы использовали свойство списочных представлений, где

  [ ... | ... <- (xs   ++   ys)] 
=== 
  [ ... | ... <- xs ] ++ [ ... | ... <- ys]

, поэтомучто

  [ ... | ... <- (x : ys)] 
=== 
  [ ... | ... <- [x] ] ++ [ ... | ... <- ys]

f a дает те же результаты, что и iterate (* a) 1, но в функциональном отношении это очень сильно отличается.В то время как последний является линейным, первый является квадратичной функцией по своей временной сложности.

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

> f 1.01 !! 4000
1.9297236994732192e17
(1.28 secs, 1614556912 bytes)

> iterate (* 1.01) 1 !! 4000
1.9297236994732192e17
(0.00 secs, 12990984 bytes)