переполнения стека в OCaml и F #, но не в Haskell

Question

Я сравнение для удовольствия разных языков для скорости при выполнении следующей программы: для I от 1 до 1000000 суммы произведения я * (SQRT I)

Одна из моих реализаций (а не единственная) создает список [1..1000000], а затем складывается с определенной функцией.

Программа работает нормально и быстро в Haskell (даже при использовании foldl, а не foldl), но переполняет стек в OCaml и F #.

Вот код Haskell:

test = foldl (\ a b -> a + b * (sqrt b)) 0 

create 0 = [] 
create n = n:(create (n-1)) 

main = print (test (create 1000000)) 

А вот OCaml один:

let test = List.fold_left (fun a b -> a +. (float_of_int b) *. (sqrt (float_of_int b))) 0. ;; 

let rec create = function 
    | 0 -> [] 
    | n -> n::(create (n-1)) ;; 

print_float (test (create 1000000));; 

Почему OCaml/F # реализации переполнение стека?

Answer 1

Код Haskell для create оценивает этот список лениво, то есть в качестве элементов необходим foldl. Весь список не нужен все сразу.

Наоборот, F # и OCaml строго определяют список create, то есть код пытается сгенерировать весь список за один проход до передачи его до fold_left.

Одна из возможностей в F # заключается в использовании выражения seq в функции create: это генерирует список лениво так же, как и Haskell. (Я не уверен, имеет ли OCaml эквивалентную функцию.)

Answer 2

В этой форме ваша функция create не является хвостовой рекурсивной. Вы можете переписать его в хвост рекурсивной форме, которая не вызывает переполнение стека:

let rec create n l = 
    match n with 
    | 0 -> l 
    | n -> create (n-1) (n::l) 

print_float (test (create 1000000 []));; 

Answer 3

Другой способ исправить код так, что он работает в F # является использование выражений последовательности, которые также генерируются лениво и в путь, который не вызывает StackOverflow (это не будет работать в OCaml, так как выражения последовательности заданы как F #). Вот код:

let test nums = Seq.fold (fun a b -> 
    a + (float b) * (sqrt (float b))) 0.0 nums 

let rec create count = seq { 
    match count with 
    | 0 -> do() 
    | n -> yield n 
     yield! create (n-1) } 

printf "%f" (test (create 1000000));; 

Я не уверен, о производительности, однако компилятор определенно делает оптимизацию в функции create, так что итерация сгенерированной последовательности должна быть достаточно быстро. Тем не менее, цель выражения последовательности - это в основном читаемость (поскольку F # не является чистым, это дает вам много места для ручных оптимизаций, если вам действительно нужны они, а не Haskell, которым нужно оптимизировать чистый код, который вы пишете). В любом случае, если у вас есть какие-то тесты, вы можете попробовать!

Answer 4

Во-первых, если вы выполняете сравнение производительности для числовых элементов, списки не являются лучшим выбором. Попробуйте пакет, такой как пакет vector для быстрых массивов.

Обратите внимание, что вы можете сделать еще лучше в Haskell благодаря слиянию с петлями. Записывая функцию create в качестве перечисления, компилятор может объединить шаг create и цикл fold в один цикл, который не выделяет промежуточных структур данных. Способность делать общий синтез, подобный этому, уникальна для GHC Haskell.

Я буду использовать векторную библиотеку (слитый цикл потока на основе):

import qualified Data.Vector as V 

test = V.foldl (\ a b -> a + b * sqrt b) 0 

create n = (V.enumFromTo 1 n) 

main = print (test (create 1000000)) 

Теперь, перед тем, с кодом, компилятор не может удалить все списки, и мы в конечном итоге с внутренним цикл, как:

$wlgo :: Double# -> [Double] -> Double# 

$wlgo = 
    \ (ww_sww :: Double#) (w_swy :: [Double]) -> 
    case w_swy of _ { 
     [] -> ww_sww; 
     : x_aoY xs_aoZ -> 
     case x_aoY of _ { D# x1_aql -> 
     $wlgo 
      (+## 
      ww_sww (*## x1_aql (sqrtDouble# x1_aql))) 
      xs_aoZ 
     } 
    } 

$wcreate :: Double# -> [Double] 

$wcreate = 
    \ (ww_swp :: Double#) -> 
    case ==## ww_swp 0.0 of _ { 
     False -> 
     : 
      @ Double 
      (D# ww_swp) 
      ($wcreate (-## ww_swp 1.0)); 
     True -> [] @ Double 
    } 

Обратите внимания, как есть две петель: создание генераторных (отложенный) список, и складка потребляющей его. Благодаря лени, стоимость этого списка является дешевой, поэтому он работает в респектабельном:

$ time ./C 
4.000004999999896e14 
./C 0.06s user 0.00s system 98% cpu 0.058 total 

При слиянии, однако, мы получаем вместо одного цикла только!

main_$s$wfoldlM_loop :: Double# -> Double# -> Double# 

main_$s$wfoldlM_loop = 
    \ (sc_sYc :: Double#) (sc1_sYd :: Double#) -> 
    case <=## sc_sYc 1000000.5 of _ { 
     False -> sc1_sYd; 
     True -> 
     main_$s$wfoldlM_loop 
      (+## sc_sYc 1.0) 
      (+## 
      sc1_sYd (*## sc_sYc (sqrtDouble# sc_sYc))) 

GHC сократил наши шаги по созданию и тестированию в один цикл без использования списков. Всего 2 рекорда в регистрах. И с половиной, как много циклов, он работает почти в два раза быстрее:

$ ghc D.hs -Odph -fvia-C -optc-O3 -optc-march=native -fexcess-precision --make 
$ time ./D 
4.000005000001039e14 
./D 0.04s user 0.00s system 95% cpu 0.038 total 

Это хороший пример силы, что гарантии чистоты обеспечивают - компилятор может быть очень агрессивен Reording кода.

Answer 5

Программа работает нормально и быстро в Haskell (даже при использовании foldl, а не foldl '), но переполнение стека в OCaml и F #.

Ваш Haskell использует ленивые списки, но ваш OCaml/F # использует строгие списки, поэтому ваши программы несравнимы.

FWIW, раствор с использованием последовательности по требованию в F # является:

Seq.sumBy (fun i -> let i = float i in i * sqrt i) (seq {1..1000000})