|
List Info
Thread: "ocaml_beginners"::[] Fibbonachi list
|
|
| "ocaml_beginners"::[]
Fibbonachi list |
|
2006-12-15 02:30:27 |
|
Hi,
Can someone tell me please what is wrong here? I'm trying to build n-elements of Fibbonachi list.
# let rec fibonacci x =
match x with
0 -> 1
| 1 -> 1
| n -> fibonacci (x - 1) + fibonacci (x - 2);;
val fibonacci : int -> int = <fun>;
# fibonacci 5;;
- : int = 8
let fib n = let rec fib n lst =
match n with
0 -> [1]
| 1 -> [1]
| m -> fib (n-1) (lst [fibonacci m])
in fib n [];;
Can someone also show me please codes of building lists for the examples in http://www.ocaml-tutorial.org/write_a_list_generator
Thanks in advance,
Ty
---------------------------------
Everyone is raving about the all-new Yahoo! Mail beta.
[Non-text portions of this message have been removed]
__._,_.___
.
__,_._,___
|
| "ocaml_beginners"::[]
Fibbonachi list |
|
2006-12-15 03:25:53 |
|
Here's some Lisp code that may help. Didn't have time
to do the translation.
(define (fib n)
(cond ((zero? n) 1)
((= n 1) 1)
(else (+ (fib (- n 1)) (fib (- n 2))))))
(define (list-fib n)
(list-fib-aux n '()))
(define (list-fib-aux n l)
(cond ((zero? n) (cons (fib n) l))
(else (cons (fib n) (list-fib-aux (- n 1)
l)))))
> (list-fib 4)
(5 3 2 1 1)
>
Michael
--- Tyson Fugel < tfugel%40yahoo.com">tfugelyahoo.com> wrote:
> Hi,
> Can someone tell me please what is wrong here? I'm
> trying to build n-elements of Fibbonachi list.
>; # let rec fibonacci x =
> match x with
> 0 -> 1
> | 1 -> 1
> | n -> fibonacci (x - 1) + fibonacci (x - 2);;
> val fibonacci : int -> int = <fun>;
> # fibonacci 5;;
> - : int = 8
>
> let fib n = let rec fib n lst =
> match n with
> 0 -> [1]
> | 1 -> [1]
> | m -> fib (n-1) (lst[fibonacci m])
> in fib n [];;
> Can someone also show me please codes of building
> lists for the examples in
> http://www.ocaml-tutorial.org/write_a_list_generator
>
>
> Thanks in advance,
> Ty
>
>
> ---------------------------------
> Everyone is raving about the all-new Yahoo! Mail
> beta.
>;
> [Non-text portions of this message have been
> removed]
>
>
__________________________________________________________
Do you Yahoo!?
Everyone is raving about the all-new Yahoo! Mail beta.
http://new.mail.yahoo.com
__._,_.___
.
__,_._,___
|
| "ocaml_beginners"::[]
Fibbonachi list |
|
2006-12-15 04:27:40 |
|
Here's the Ocaml code to replace the earlier Lisp.
Hope it's what you were looking for.
# let rec fib n =
match n with
0 -> 1
| 1 -> 1
| m -> fib (n-1) + fib (n-2);;
val fib : int -> int = <fun>;
# let rec list_fib_aux = function
(0,l) -> fib 0 :: l
| (n,l) -> fib n :: list_fib_aux (n-1,l);;
val list_fib_aux : int * int list -> int list = <fun>;
#
# let list_fib n = List.rev(list_fib_aux (n,[]));;
val list_fib : int -> int list = <fun>;
# list_fib 4;;
- : int list = [1; 1; 2; 3; 5]
#
Michael
--- Tyson Fugel < tfugel%40yahoo.com">tfugelyahoo.com> wrote:
> Hi,
> Can someone tell me please what is wrong here? I'm
> trying to build n-elements of Fibbonachi list.
>; # let rec fibonacci x =
> match x with
> 0 -> 1
> | 1 -> 1
> | n -> fibonacci (x - 1) + fibonacci (x - 2);;
> val fibonacci : int -> int = <fun>;
> # fibonacci 5;;
> - : int = 8
>
> let fib n = let rec fib n lst =
> match n with
> 0 -> [1]
> | 1 -> [1]
> | m -> fib (n-1) (lst[fibonacci m])
> in fib n [];;
> Can someone also show me please codes of building
> lists for the examples in
> http://www.ocaml-tutorial.org/write_a_list_generator
>
>
> Thanks in advance,
> Ty
>
>
> ---------------------------------
> Everyone is raving about the all-new Yahoo! Mail
> beta.
>;
> [Non-text portions of this message have been
> removed]
>
>
__________________________________________________________
Have a burning question?
Go to www.Answers.yahoo.com and get answers from real people who know.
__._,_.___
.
__,_._,___
|
| "ocaml_beginners"::[]
Fibbonachi list |
|
2006-12-15 04:26:15 |
|
Hi Tyson,
I'm a beginner myself but I think it works like this.
The fibonacci function is ok (although the Fibonacci number of 0 is 0,
I think). Use this and then add the function.
let rec fib n lst =
match n with
0 -> 0 :: lst
| 1 -> 1 :: lst
| m -> fib (n-1) ((fibonacci m) :: lst);;
This should do the trick. You will get the Fibonacci number for all
numbers 1..n.
Here's an example:
# fib 10 [];;
- : int list = [1; 2; 3; 5; 8; 13; 21; 34; 55; 89]
Cheers,
Christian
Am Thu, 14 Dec 2006 18:30:27 -0800 (PST)
schrieb Tyson Fugel < tfugel%40yahoo.com">tfugelyahoo.com>:
> Hi,
> Can someone tell me please what is wrong here? I'm trying to build
>; n-elements of Fibbonachi list. # let rec fibonacci x =
> match x with
> 0 -> 1
> | 1 -> 1
> | n -> fibonacci (x - 1) + fibonacci (x - 2);;
> val fibonacci : int -> int = <fun>;
> # fibonacci 5;;
> - : int = 8
>
> let fib n = let rec fib n lst =
> match n with
> 0 -> [1]
> | 1 -> [1]
> | m -> fib (n-1) (lst[fibonacci m])
> in fib n [];;
> Can someone also show me please codes of building lists for the
> examples in http://www.ocaml-tutorial.org/write_a_list_generator
> Thanks in advance,
> Ty
>
>
> ---------------------------------
> Everyone is raving about the all-new Yahoo! Mail beta.
>;
> [Non-text portions of this message have been removed]
>
__._,_.___
.
__,_._,___
|
| "ocaml_beginners"::[]
Fibbonachi list |
|
2006-12-15 04:34:20 |
|
__,_._,___
|
| "ocaml_beginners"::[]
Fibbonachi list |
|
2006-12-15 20:35:05 |
|
On Thu, 14 Dec 2006, Tyson Fugel wrote:
> Hi,
> Can someone tell me please what is wrong here? I'm trying to build
> n-elements of Fibbonachi list.
>;
> let fib n = let rec fib n lst =
> match n with
> 0 -> [1]
> | 1 -> [1]
> | m -> fib (n-1) (lst[fibonacci m])
> in fib n [];;
OK, while others have shown you correct ways to write a Fibonacci list
generator, they haven't shown you what your problem was in the first
place, which might be beneficial.
The problem with your code is that while you do build up the list of
Fibonacci numbers with your (lst[fibonacci m]) construct, you end up
throwing that list away when you hit your base cases. To see this
clearly, let's look at a simple example:
fib 3 -> fib 3 [] (by the befinition of the outer fib)
fib 3 [] -> fib 2 ([][3]) (by the inner fib definition, match case 3)
fib 2 [2] -> fib 1 ([3][2]) (by the inner fib definition, match case 3)
fib 1 [3; 2] -> [1] (by the inner fib, match case 2)
And so we return [1], throwing away the construction of the rest of the
list, [3;2]. If you want to build the list that way, you need to prepend
lst to [1] before returning. E.g.
let fib n =
let rec fib' n lst =
match n with
0 -> lst[1]
| 1 -> lst[1]
| m -> fib' (n-1) (lst[fibonacci m])
in fib' n [];;
> Can someone also show me please codes of building lists for the
> examples in http://www.ocaml-tutorial.org/write_a_list_generator
Let's build up to this with a quick observation about the Fibonacci list
(note that we'll be building this list facing the other direction, with
the ith fib number in position n-i):
If we start with the list [1;0], we don't really need to call the
fibonacci function to generate the next member in our series, because all
we need to do is add the first two elements of the current list, add them
together, then add that value to the left of the current list. E.g.
Fib(1) = [1;0]
Fib(2) = (1+0)::[1;0] = [1;1;0]
Fib(3) = (1+1)::[1;1;0] = [2;1;1;0]
...
Fib(n) = match Fib(n-1) with a::b::_ -> (a+b)::Fib(n-1)
This can be expressed in OCaml as follows:
let fib_list n=
let rec fl_aux = function
| 0,_ -> [0] (* special case to handle a truncation of the base case *)
| k,l when k >= n -> l (* we've reached the end of the recursive
build... return the result*)
| k,((h1::h2::_) as l) -> fl_aux (k+1,(h1+h2)::l) (* add another value
to the build and
recurse *)
| _ -> assert false (* this should never happen *)
in
fl_aux (1,[1;0])
;;
And, of course, if you want the final result to point the other direction,
just use List.rev l for the action in the second match case.
So, now the idea is to try to generalize this idea. To pull out the
essential parts (having a list of cases n-0), and using some function of
those cases to build case n+1 from the previous n cases according to some
rule, gen. First we'll show how to do this in the more or less natural
way (i.e. with case i being in position i in the list):
To create such a function, we really have two cases to worry about: the
case where gen(i) is in our list of base cases, and the case when it is
not.
(* not necessarily essential aside *)
Now... we hit a tiny snag here. If we want to be general, we need gen to
let us know that the base cases we need aren't in the set we hand it, in
which case, we'd need to build up the base cases and try again -- this is
a bit messier, requiring us to check gen for exceptions (we could use
variants, but then we don't match the signature shown in <1>) and then
handle them appropriately... bleah. Instead, what we will do is simply
build up the base cases until they hold the info for cases 0 through n-1,
and we're sure to satisfy any well-formed rule gen, which is cool, as we
need to build up those cases anyway as they're part of what we're supposed
to return.
(* end of aside *)
OK, so what we do is simple: if there are b elements in the list of base
cases, we check to see if b+1 is greater than n (i.e. gen(b) is in the
list of base cases), if it is, we simply return the base cases (perhaps
truncating it if n < b). Otherwise, we compute element b+1 from the set
of b base cases we have, add it to the list of base cases then recurse
until the list of base cases is as big as needed. We can do this as
follows:
let build_list gen b n =
(* take is our truncation routine, where take l n returns the first
(n+1) elements of l -- we need (n+1), as the first element
corresponds to base case 0
*)
let rec take l = function
| -1 -> []
| n -> (match l with [] -> [] | h::t -> h::(take t (n-1)))
in
let rec bl_aux bases = function
| k when k > n -> bases
| k -> bl_aux (bases[gen bases k]) (k+1)
in
take (bl_aux b (List.length b)) n
;;
let fact =
build_list (fun bases n -> n * (List.nth bases (n-1))) [1]
;;
let fibo =
build_list
(fun bases n ->
let u = List.nth bases in
(u (n-1)) + (u (n-2)))
[0; 1]
;;
Now, there's still a bit of a problem here, and that's that we are using
to build our lists on the right. This doesn't make the program incorrect,
but it's inefficient, leading to an O(n^2) algorithm rather than O(n) --
not a big deal for short lists, but for longer ones, it becomes an issue.
Note that this problem is exacerbated by our need to use List.nth when
defining gen. Chances are we're going to have to walk nearly the entire
lenght of the base case list to find the one we want -- again, for longer
lists this will be an issue). And finally, append is not tail recursive,
and will die on really long lists.
So what we can do instead, is build the base case list from the left,
using :: instead of . This fixes all of our problems above, as consing
is a constant time operation, it keeps the values we need for the
recurrance close to the starting point of the list, and it admits a tail
recursive solution.
let build_list2 gen b n =
(* like take above, only this returns the last n+1 elements of l *)
let last l n =
let rec t_aux acc = function
| -1,_ | _,[] -> acc
| n,h::t -> t_aux (h::acc) (n-1,t)
in
if n >= List.length l then l
else t_aux [] (n,List.rev l)
in
let rec bl_aux bases = function
| k when k > n -> bases
| k -> bl_aux ((gen bases k)::bases) (k+1)
in
last (bl_aux b (List.length b)) n
;;
let fact2 =
build_list2 (fun bases n -> n * (List.hd bases)) [1]
;;
let fibo2 =
build_list2
(fun bases n ->
match bases with
| a::b::_ -> a+b
| _ -> assert false)
[1; 0];;
Note that in this style, the gen rule pulls the values from the left end
of the list (you could, of course, use List.nth, but where you would use
List.nth l i in the first version, you would need List.nth l (k-i) here).
Also, you need to reverse the order of the base cases from the previous
version.
# fact 5;;
fact2 5;;
- : int list = [1; 1; 2; 6; 24; 120]
# - : int list = [120; 24; 6; 2; 1; 1]
# fibo 11;;
fibo2 11;;
- : int list = [0; 1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89]
# - : int list = [89; 55; 34; 21; 13; 8; 5; 3; 2; 1; 1; 0]
Anyway, I hope that helps more than confuses.
<1>; <http://www.ocaml-tutorial.org/write_a_list_generator>
William D. Neumann
---
"There's just so many extra children, we could just feed the
children to these tigers. We don't need them, we're not doing
anything with them.
Tigers are noble and sleek; children are loud and messy."
-- Neko Case
Life is unfair. Kill yourself or get over it.
-- Black Box Recorder
__._,_.___
.
__,_._,___
|
[1-6]
|
|