Зачем нужен Haskell:



Зачем нужен Haskell:

0 0


rif2015lazy

Презентация для РИФ-Воронеж 2015

On Github denisshevchenko / rif2015lazy

Зачем нужен Haskell:

ленивые вычисления

В начале было…

λ-исчисление

 λx.x + 1
(λx.x + 1) 6
(λx.x + 1) 2 * 3
(λx.x + 1) 2 * 3
(λx.x + 1) 6
(λx.x + 1)  ⇒  6 + 1
Жадное вычисление
(λx.x + 1)  ⇒  6 + 1
(λx.x + 1) 2 * 3
(λx.x + 1)  ⇒  (2 * 3) + 1
Ленивое вычисление
(λx.x + 1)  ⇒  (2 * 3) + 1

Киты

1
Как можно позже
main =
  let result = 2 `div` 0
  in print result
                    
Ошибка
main =
  let result = 2 `div` 0
  in putStr "Bye!"
                    
Нет ошибки

2
Как можно меньше
main =
  let cx     = 2 / 6.054
      nk     = 4 * 12.003
      coeffs = [cx, nk]
  in putStr "Nothing..."
                    
Ничего
Thunk
main =
  let cx     = 2 / 6.054
      nk     = 4 * 12.003
      coeffs = [cx, nk]
  in print $ length coeffs
                    
Только длина
WHNF
main =
  let cx     = 2 / 6.054
      nk     = 4 * 12.003
      coeffs = [cx, nk]
  in print $ coeffs !! 1
                    
Только второй
WHNF
main =
  let cx     = 2 / 6.054
      nk     = 4 * 12.003
      coeffs = [cx, nk]
  in print coeffs
                    
Всё
Normal form

Зачем это нам?

1
Рациональность
main =
  let evens = [2, 4 .. 100]
  in print $ take 10 evens
                    
Столько, сколько нужно

2
Бесконечность
main =
  let evens = [2, 4 ..]
  in print $ take 10 evens
                    
Не более десяти

3
EDSL
(?) :: Bool -> (a, a) -> a
True  ? (f, _) = f
False ? (_, s) = s
                    
Замена if
main = do
  putStr "Input URL prefix: "
  prefix <- getLine
  (prefix == "https") ?
    (putStr "Secure web!",
     exitFailure)
                    

Но…

Space leak
Space leak ≠ Memory leak
main =
  let result = 2 `div` 0
  in putStr "Bye!"
                    
Деления не было
И сколько же будет отложенных выражений?
bad :: Num b => [a] -> b -> b
bad []     c = c
bad (_:xs) c = bad xs $ c + 1
                    
Проблема
bad [1,2,3] 0
                    
Применяем…
bad 1:[2,3] 0 + 1
                    
Первый шаг…
bad 1:2:[3] (0 + 1) + 1
                    
Второй…
bad 1:2:3:[] ((0 + 1) + 1) + 1
                    
Третий и последний…
((0 + 1) + 1) + 1 = 3
                    
Вычисляем
main =
  print $ bad [1..50000000] 0
                    
63 с
6.4 ГБ

Что же делать?

1
Оптимизация
-O0 -O2 63 c 3.2 с 6.4 ГБ 104 кБ

2
Ручками
ok :: Num b => [a] -> b -> b
ok []     c = c
ok (_:xs) c = ok xs $! c + 1
                    
Добавляем строгости
Лениво Строго 63 c 5.8 с 6.4 ГБ 182 кБ

Итак…

Как можно позже Как можно меньше
Рациональность Бесконечность EDSL
Space leak
Благодарю!
Денис Шевченко • dshevchenko.biz
Зачем нужен Haskell: ленивые вычисления