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

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

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

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

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

И обратите внимание, что вы можете добиться еще большего успеха в Haskell благодаря слиянию циклов. Написав функцию создания в виде перечисления, компилятор может объединить этап создания и цикл свертывания в один цикл, который не выделяет промежуточных структур данных. Подобная возможность общего слияния уникальна для 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
    }

Обратите внимание на два цикла: create, генерирующий (ленивый) список, и fold, потребляющий его. Из-за лени стоимость этого списка дешева, поэтому он выглядит прилично:

$ 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

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

Еще один способ исправить код так, чтобы он работал в 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, которому нужно оптимизировать чистый код, который вы пишете). В любом случае, если у вас есть тесты, вы можете попробовать!

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

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

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

Программа отлично и быстро работает в 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})