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

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

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

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

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

В таком виде ваша функция 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})