Haskell, tail recursion, hugs, ДНК или лопата?

Там при выводе получается охрениииииииительное число, вот и неможет его вывести. А код на C не покажешь?

[krum@localhost haskell]$ cat test.c
#include <stdio.h>
#include <stdlib.h>
unsigned int fact(unsigned int acc, unsigned int n){
       if ( n == 0 ) return acc;
       if ( n >  0 ) return fact( acc*n, n-1);
}
int main(int argc, char **argv){
       if(argc<2) {printf(" usage: fact <n> \n"); return 0;}
       printf(" fact %d = %d \n", atoi(argv[1]), fact(1,atoi(argv[1])));
       return 0;
}
[krum@localhost haskell]$ gcc -O3 test.c -o fact
[krum@localhost haskell]$ ./fact 1000000
 fact 1000000 = 0
[krum@localhost haskell]$ gcc -O0 test.c -o fact_O0
[krum@localhost haskell]$ ./fact_O0 1000000
Ошибка сегментирования

Конечно для чистоты эксперимента нужно использовать gmp для больших чисел, но тут, имхо, без разницы. Вот кстати ассемблерный вывод fact с -O3 и с -O0:

-O0:
.globl fact
        .type   fact, @function
fact:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $16, %esp
        cmpl    $0, 12(%ebp)
        jne     .L2
        movl    8(%ebp), %eax
        movl    %eax, -4(%ebp)
        jmp     .L4
.L2:
        cmpl    $0, 12(%ebp)
        je      .L5
        movl    12(%ebp), %edx
        subl    $1, %edx
        movl    8(%ebp), %eax
        imull   12(%ebp), %eax
        movl    %edx, 4(%esp)
        movl    %eax, (%esp)
        call    fact
        movl    %eax, -4(%ebp)
        jmp     .L4
.L5:
        jmp     .L1
.L4:
        movl    -4(%ebp), %eax
        movl    %eax, -8(%ebp)
.L1:
        movl    -8(%ebp), %eax
        leave
        ret
        .size   fact, .-fact
        .section        .rodata


-O2 ( потому что -O3 использует какую-то изощрённую оптимизацию, которая ту не важна):

.globl fact
        .type   fact, @function
fact:
        pushl   %ebp
        movl    %esp, %ebp
        movl    12(%ebp), %edx
        movl    8(%ebp), %eax
        testl   %edx, %edx
        je      .L3
        .p2align 4,,7
.L7:
        imull   %edx, %eax
        subl    $1, %edx
        jne     .L7
.L3:
        popl    %ebp
        ret
        .size   fact, .-fact

Ясно. Только в C у тебя не влезет в int то число, которое получается, оно получается усечённым по модулю sizeof(unsigned int). А алгоритм на хаскеле правильный, можешь же вывести fact 10000, например, за небольшое время. А вообще, fact n = product [1..n] ;)

Даже ghc говорит, что Stack space overflow: :((( Ну не может же быть, что бы haskell не поддерживал хвостовую рекурсию:( На этот вариант fact n = product [1..n] он то же самое говорит.

Проблема НЕ В ХВОСТОВОЙ РЕКУРСИИ. Проблема в выводе этого числа. Там получается примерно несколько мегабайт число. И переполнение стека не в рекурсии происходит.

Дело в том Haskell использует lazy, а не eage evalution. 

т.е если считать факториал как вы, т.е 

fact a n = if n == 0 then a else fact (a*n) (n-1)

последовательность выражений при вычисление fact 10 будет примерно такой:

fact 10
fact (10*9) 9
fact (10*9*8) 7 , и т.д

То бишь он сначала запишет выражение 10*9*8*7..*1,
а потом будет его вычислять. 

по идее должно помочь seq. т.e:

fact a n = if n == 0 then 1 else let {b = a*n} in seq b (fact b (n-1))

//PS hugs под рукой нет, но по идее должно сработать

Не, то же самое:( Блин, в то же схеме всё проще.

Похоже Вы правы, тк заменив a*n на 1 перестал падать.

Не, не правы:) Вот так тоже падает:module Main where import IO

fact :: Integer -> Integer -> Integer fact a n = case n of 0 -> a n | n < 0 -> 0 n -> fact (a+1) (n-1)

main :: IO () main = do putStr "Enter a number: " hFlush stdout str <- getLine let num = read str resnum = fact 1 num putStrLn $ "result: " ++ show resnum При num = 99999

Не, не правы:) Вот так тоже падает:module Main where
import IO

fact :: Integer -> Integer -> Integer
fact a n =  case n of
        0 -> a
        n | n < 0 -> 0
        n -> fact (a+1) (n-1)

main :: IO ()
main = do
    putStr "Enter a number: "
    hFlush stdout
    str <- getLine
    let num = read str
        resnum = fact  1  num
    putStrLn $ "result: " ++ show resnum
При num = 99999

Дело похоже в hugs. Следующий код, будучи откомпилирован ghc, выдает
ответ и для 99999 (правда через довольно длительное время):

import IO

fact a n = case n of
             0         -> a
             n | n < 0 -> 0
             n         -> fact (a + 1) (n - 1)

main :: IO ()

main = do
  putStr "Enter a number: "
  hFlush stdout
  str <- getLine
  let num = read str
      resnum = fact 1 num
  putStrLn $ "result: " ++ show resnum

Ответ не привожу, он очень большой.

Вообще для 99999 должно выдать 1000000, тут же просто на каждом шаге добавляется 1. А вот с 999999 падает:( 
krum@localhost haskell]$ cat test1.hs
import IO

fact a n = case n of
             0         -> a
             n | n < 0 -> 0
             n         -> fact (a + 1) (n - 1)

main :: IO ()

main = do
  putStr "Enter a number: "
  hFlush stdout
  str <- getLine
  let num = read str
      resnum = fact 1 num
  putStrLn $ "result: " ++ show resnum
[krum@localhost haskell]$ ghc test1.hs
[krum@localhost haskell]$ ./a.out
Enter a number: 99999
result: 100000
[krum@localhost haskell]$ ./a.out
Enter a number: 999999
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize' to increase it.

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

Но, ты прав, у ghc лишь больший стек...