[Caml-list] Function composition in CAML

[Caml-list] Function composition in CAML

[TBraibant]

[-- Attachment #1: Type: text/plain, Size: 694 bytes --]

Hello

I have made some experimentations, but I can't find where is a bug in a simple piece of code

I represent a polynome by a list of its coefficents
(I know that there is a more efficient way to do this calculation (P(x) in fact), but it is just an expermimentation)

let horner p x =
  let v= Array.of_list p in
  let n = Array.length v in
  let r = ref n in 
  let f = ref (function u ->u  ) in
    while !r <> 0 do
      f := (function u -> !f( v.(!r)+ x*u));
      r := !r -1 ;
    done;
    !f(0)
;;

In theory, the !f(0) call shall give me P(x)...
But it seems that the computer crash, and can't handle this line of code...

Someone has an idea?

Thank you


[-- Attachment #2: Type: text/html, Size: 1901 bytes --]

Re: [Caml-list] Function composition in CAML

[Oleg Trott]

On Sunday 08 June 2003 07:27 am, TBraibant wrote:
> Hello
>
> I have made some experimentations, but I can't find where is a bug in a
> simple piece of code
>
> I represent a polynome by a list of its coefficents
> (I know that there is a more efficient way to do this calculation (P(x) in
> fact), but it is just an expermimentation)
>
> let horner p x =
>   let v= Array.of_list p in
>   let n = Array.length v in
>   let r = ref n in
>   let f = ref (function u ->u  ) in
>     while !r <> 0 do
>       f := (function u -> !f( v.(!r)+ x*u));
>       r := !r -1 ;
>     done;
>     !f(0)
> ;;
>
> In theory, the !f(0) call shall give me P(x)...
> But it seems that the computer crash, and can't handle this line of code...
>
> Someone has an idea?
>
> Thank you

The computer does not crash, you are merely entrering an infinite loop 
because, with function composition, you couldn't keep track of the mutable 
variables in your code. A possible solution is:

let eval p x = 
  let rec aux p prod sum =
    match p with
    | [] -> sum
    | a :: b -> aux b (x*prod) (a*prod + sum)
  in aux p 1 0
;;

"eval" does not implement Horner's rule. The latter sounds like homework :)

-- 
Oleg Trott <oleg_trott@columbia.edu>

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Function composition in CAML

[Frederic van der Plancke]

> I have made some experimentations, but I can't find where is a bug in a 
> simple piece of code

> I represent a polynome by a list of its coefficents
[...]
> let horner p x =
>   let v= Array.of_list p in
>   let n = Array.length v in
>   let r = ref n in 
>   let f = ref (function u ->u  ) in
>     while !r <> 0 do
>       f := (function u -> !f( v.(!r)+ x*u));
>       r := !r -1 ;
>     done;
>     !f(0)
> ;;
> 
> In theory, the !f(0) call shall give me P(x)...
> But it seems that the computer crash, and can't handle this line of code...
> 
> Someone has an idea?

Subtle !
There is an infinite recursion: operator "!" before "f" is evaluated when
the code where it lies is evaluated, that is when f is called, 
hence "!f" represents the last created function f and not the one you want. 
You should evaluate "!f" outside of (function u -> ....), or (better) 
rewrite your loop using a recursive function taking "the current r" and
(maybe) "the current f" as argument(s).

(There's also an independent bug which will yield an out-of-bound array 
access error...)

Frédéric vdP

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners