Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /archive/0.93/doc/examples/stream.sml
ViewVC logotype

Annotation of /archive/0.93/doc/examples/stream.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4958 - (view) (download)

1 : dbm 4958 (* stream.sml *)
2 :    
3 :     (* streams as a structure *)
4 :     (* The type is named stream to avoid conflict with the i/o type stream *)
5 :    
6 :     signature STREAM =
7 :     sig
8 :     type 'a stream
9 :     val lazyCons: (unit -> '1a * '1a stream) -> '1a stream
10 :     and cons: '1a * '1a stream -> '1a stream
11 :     and head: 'a stream -> 'a
12 :     and tail: 'a stream -> 'a stream
13 :     and prefix : int -> 'a stream -> 'a list
14 :     and lazyMap : ('1a -> '1b) -> '1a stream -> '1b stream
15 :     end
16 :    
17 :     structure Stream : STREAM =
18 :     struct
19 :     datatype 'a stream = STREAM of 'a str ref
20 :     and 'a str = SOLID of 'a * 'a stream
21 :     | SUSPENDED of unit -> ('a * 'a stream);
22 :     fun solidify(STREAM(ref(SOLID p))) = p
23 :     | solidify(STREAM(s as ref(SUSPENDED f))) =
24 :     let val p = f() in (s := SOLID p; p) end
25 :     fun lazyCons(f) = STREAM(ref(SUSPENDED f))
26 :     fun cons(x,ss) = STREAM(ref(SOLID(x,ss)))
27 :     fun head s = let val (hd,_) = solidify s in hd end
28 :     fun tail s = let val (_,tl) = solidify s in tl end
29 :     fun prefix 0 s = nil
30 :     | prefix n s = (head s)::(prefix (n-1) (tail s))
31 :     fun lazyMap f s =
32 :     let fun g (STREAM(ref(SOLID(x, s)))) = lazyCons(fn () => (f x, g s))
33 :     | g (s) = lazyCons
34 :     (fn () => let val (x, s') = solidify s in (f x, g s') end)
35 :     in lazyCons(fn () => solidify(g s))
36 :     end
37 :     end;
38 :    
39 :     open Stream;
40 :    
41 :     val nats = (* stream of natural numbers *)
42 :     let fun f n = lazyCons(fn () => (n, f(n+1)));
43 :     in f 0
44 :     end;
45 :    
46 :     fun add(s1: int stream, s2: int stream) =
47 :     lazyCons(fn () => (head s1 + head s2, add(tail s1, tail s2)));
48 :    
49 :     val fibs = (* stream of fibonaci numbers *)
50 :     let fun f () = cons(1,lazyCons(fn () =>
51 :     (1,let val s = f() in add(s, tail s) end)))
52 :     in f ()
53 :     end;

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0