8 people like it.

Iteratee

An iteratee based on https://john-millikin.com/software/enumerator/ and http://okmij.org/ftp/Haskell/Iteratee/IterateeIO-talk-notes.pdf

Iteratee

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
/// A stream of chunks of data generated by an Enumerator.
/// The stream can be composed of chunks of 'a, empty blocks indicating a wait, or an EOF marker.
/// In Haskell, the Chunk is usually composed of a list of ListLike type, but F# doesn't support
/// Monad Transforms or ^M in type declarations. Thus, the Chunk is left open to various internal
/// types, but a bit more work must be done in order to maintain the meaningfulness of "chunk".
/// That said, the 'a allows a large number of chunk-y types to be used, including other monads.
/// Be aware that when using #seq<_> types, you will need to check for both Seq.empty ([]) and Empty.
type Stream<'a> =
  | Chunk of 'a
  | Empty
  | EOF

/// The iteratee is a stream consumer that will consume a stream of data until either 
/// it receives an EOF or meets its own requirements for consuming data. The iteratee
/// will return Continue whenever it is ready to receive the next chunk. An iteratee
/// is fed data by an Enumerator, which generates a Stream. 
type Iteratee<'el,'acc> =
  | Continue of (Stream<'el> -> Iteratee<'el,'acc>)
  | Yield of 'acc * Stream<'el>
  | Error of exn

/// An enumerator generates a stream of data and feeds an iteratee, returning a new iteratee.
type Enumerator<'el,'acc> = Iteratee<'el,'acc> -> Iteratee<'el,'acc>

/// An Enumeratee is an Enumerator that feeds data streams to an internal iteratee.
type Enumeratee<'elo,'eli,'acc> = Iteratee<'eli,'acc> -> Iteratee<'elo, Iteratee<'eli,'acc>>

// TODO: Make calls to bind tail recursive.
let rec bind m f =
  match m with
  | Continue k -> Continue(fun s -> bind (k s) f)
  | Error e -> Error e
  | Yield(x, Empty) -> f x
  | Yield(x, extra) ->
      match f x with
      | Continue k -> k extra
      | Error e -> Error e
      | Yield(acc',_) -> Yield(acc', extra)

let combine comp1 comp2 =
  let binder () = comp2
  bind comp1 binder

type IterateeBuilder() =
  member this.Return(x) = Yield(x, Empty)
  member this.ReturnFrom(m:Iteratee<_,_>) = m
  member this.Bind(m, k) = bind m k
  member this.Zero() = Yield((), Empty)
  member this.Combine(comp1, comp2) = combine comp1 comp2
  member this.Delay(f) = bind (Yield((), Empty)) f
let iteratee = IterateeBuilder()

Iteratee runners

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
let rec enumEOF = function
  | Yield(x,_) -> Yield(x,EOF)
  | Error e -> Error e
  | Continue k ->
      match k EOF with
      | Continue _ -> failwith "enumEOF: divergent iteratee"
      | i -> enumEOF i

let run i =
  match enumEOF i with
  | Error e -> Choice1Of2 e
  | Yield(x,_) -> Choice2Of2 x
  | Continue _ -> failwith "run: divergent iteratee"

let run_ i =
  match run i with
  | Choice1Of2 e -> raise e
  | x -> x

Sample iteratees

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
65: 
66: 
67: 
let length<'a> : Iteratee<'a list, int> =
  let rec step n = function
    | Empty | Chunk [] -> Continue (step n)
    | Chunk x          -> Continue (step (n + 1))
    | EOF         as s -> Yield(n, s)
  Continue (step 0)

let rec peek =
  let rec step = function
    | Empty | Chunk []  -> peek
    | Chunk(x::xs) as s -> Yield(Some x, s)
    | s                 -> Yield(None, s)
  Continue step

let rec head =
  let rec step = function
    | Empty | Chunk [] -> head
    | Chunk(x::xs)     -> Yield(Some x, (Chunk xs))
    | EOF              -> Yield(None, EOF)
  Continue step

let rec drop n =
  let rec step = function
    | Empty | Chunk [] -> Continue step
    | Chunk x          -> drop (n - 1)
    | EOF         as s -> Yield((), s)
  if n = 0 then Yield((), Empty) else Continue step

let split (pred:char -> bool) =
  let rec step before = function
    | Empty | Chunk [] -> Continue (step before)
    | Chunk str ->
        match List.split pred str with
        | (_,[]) -> Continue (step (before @ str))
        | (str,tail) -> Yield((before @ str), Chunk tail)
    | s -> Yield(before, s)
  Continue (step [])

let heads str =
  let rec loop count str =
    match count, str with
    | (count, []) -> Yield(count, EOF)
    | (count, str) -> Continue (step count str)
  and step count str s =
    let str = List.ofSeq str
    match str, s with
    | str, Empty -> loop count str
    | str, (Chunk []) -> loop count str
    | c::t, (Chunk (c'::t')) ->
        if c = c' then step (count + 1) t (Chunk t') 
        else Yield(count, (Chunk (c'::t')))
    | _, s -> Yield(count, s)
  loop 0 str

let readLines =
  let toString chars = String(Array.ofList chars)
  let crlf = ['\r';'\n']
  let lf = ['\n']
  let isNewline c = c = '\r' || c = '\n'
  let terminators = heads crlf >>= fun n -> if n = 0 then heads lf else Yield(n, Empty)
  let rec lines acc = split isNewline >>= fun l -> terminators >>= check acc l
  and check acc l count =
    match l, count with
    | [], _ -> Yield (Choice2Of2 (List.rev acc |> List.map toString), EOF)
    | l, 0 -> Yield (Choice1Of2 (List.rev acc |> List.map toString), Chunk l)
    | l, _ -> lines (l::acc)
  lines []

Sample enumerators

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
//val enumerate :: 'a list -> Enumerator<'a list,'b>
let rec enumerate input = fun i ->
  match input, i with
  | [], Continue k -> Continue k
  | (x::xs), Continue k -> enumerate xs (k (Chunk [x]))
  | _, i -> i

// val enumeratePure1Chunk :: 'a list -> Enumerator<'a list,'b>
let enumeratePure1Chunk (str:'a list) = function
  | Continue k -> k (Chunk str)
  | i -> i

// val enumeratePureNChunk :: 'a list -> int -> Enumerator<'a list,'b>
let rec enumeratePureNChunk str n = fun i ->
  match str, i with
  | _::_, Continue k ->
      let (s1, s2) = List.splitAt n str
      enumeratePureNChunk s2 n (k (Chunk s1))
  | _, i -> i
type Stream<'a> =
  | Chunk of 'a
  | Empty
  | EOF

Full name: FSharp.Monad.Iteratee.Core.Stream<_>


 A stream of chunks of data generated by an Enumerator.
 The stream can be composed of chunks of 'a, empty blocks indicating a wait, or an EOF marker.
 In Haskell, the Chunk is usually composed of a list of ListLike type, but F# doesn't support
 Monad Transforms or ^M in type declarations. Thus, the Chunk is left open to various internal
 types, but a bit more work must be done in order to maintain the meaningfulness of "chunk".
 That said, the 'a allows a large number of chunk-y types to be used, including other monads.
 Be aware that when using #seq<_> types, you will need to check for both Seq.empty ([]) and Empty.
union case Stream.Chunk: 'a -> Stream<'a>
union case Stream.Empty: Stream<'a>
union case Stream.EOF: Stream<'a>
type Iteratee<'el,'acc> =
  | Continue of (Stream<'el> -> Iteratee<'el,'acc>)
  | Yield of 'acc * Stream<'el>
  | Error of exn

Full name: FSharp.Monad.Iteratee.Core.Iteratee<_,_>


 The iteratee is a stream consumer that will consume a stream of data until either
 it receives an EOF or meets its own requirements for consuming data. The iteratee
 will return Continue whenever it is ready to receive the next chunk. An iteratee
 is fed data by an Enumerator, which generates a Stream.
union case Iteratee.Continue: (Stream<'el> -> Iteratee<'el,'acc>) -> Iteratee<'el,'acc>
union case Iteratee.Yield: 'acc * Stream<'el> -> Iteratee<'el,'acc>
union case Iteratee.Error: exn -> Iteratee<'el,'acc>
type exn = System.Exception

Full name: Microsoft.FSharp.Core.exn
type Enumerator<'el,'acc> = Iteratee<'el,'acc> -> Iteratee<'el,'acc>

Full name: FSharp.Monad.Iteratee.Core.Enumerator<_,_>


 An enumerator generates a stream of data and feeds an iteratee, returning a new iteratee.
type Enumeratee<'elo,'eli,'acc> = Iteratee<'eli,'acc> -> Iteratee<'elo,Iteratee<'eli,'acc>>

Full name: FSharp.Monad.Iteratee.Core.Enumeratee<_,_,_>


 An Enumeratee is an Enumerator that feeds data streams to an internal iteratee.
val bind : m:Iteratee<'a,'b> -> f:('b -> Iteratee<'a,'c>) -> Iteratee<'a,'c>

Full name: FSharp.Monad.Iteratee.Core.bind
val m : Iteratee<'a,'b>
val f : ('b -> Iteratee<'a,'c>)
val k : (Stream<'a> -> Iteratee<'a,'b>)
val s : Stream<'a>
val e : exn
val x : 'b
val extra : Stream<'a>
val k : (Stream<'a> -> Iteratee<'a,'c>)
val acc' : 'c
val combine : comp1:Iteratee<'a,unit> -> comp2:Iteratee<'a,'b> -> Iteratee<'a,'b>

Full name: FSharp.Monad.Iteratee.Core.combine
val comp1 : Iteratee<'a,unit>
val comp2 : Iteratee<'a,'b>
val binder : (unit -> Iteratee<'a,'b>)
Multiple items
type IterateeBuilder =
  new : unit -> IterateeBuilder
  member Bind : m:Iteratee<'f,'g> * k:('g -> Iteratee<'f,'h>) -> Iteratee<'f,'h>
  member Combine : comp1:Iteratee<'c,unit> * comp2:Iteratee<'c,'d> -> Iteratee<'c,'d>
  member Delay : f:(unit -> Iteratee<'a,'b>) -> Iteratee<'a,'b>
  member Return : x:'k -> Iteratee<'l,'k>
  member ReturnFrom : m:Iteratee<'i,'j> -> Iteratee<'i,'j>
  member Zero : unit -> Iteratee<'e,unit>

Full name: FSharp.Monad.Iteratee.Core.IterateeBuilder

--------------------
new : unit -> IterateeBuilder
val this : IterateeBuilder
member IterateeBuilder.Return : x:'k -> Iteratee<'l,'k>

Full name: FSharp.Monad.Iteratee.Core.IterateeBuilder.Return
val x : 'k
member IterateeBuilder.ReturnFrom : m:Iteratee<'i,'j> -> Iteratee<'i,'j>

Full name: FSharp.Monad.Iteratee.Core.IterateeBuilder.ReturnFrom
val m : Iteratee<'i,'j>
member IterateeBuilder.Bind : m:Iteratee<'f,'g> * k:('g -> Iteratee<'f,'h>) -> Iteratee<'f,'h>

Full name: FSharp.Monad.Iteratee.Core.IterateeBuilder.Bind
val m : Iteratee<'f,'g>
val k : ('g -> Iteratee<'f,'h>)
member IterateeBuilder.Zero : unit -> Iteratee<'e,unit>

Full name: FSharp.Monad.Iteratee.Core.IterateeBuilder.Zero
member IterateeBuilder.Combine : comp1:Iteratee<'c,unit> * comp2:Iteratee<'c,'d> -> Iteratee<'c,'d>

Full name: FSharp.Monad.Iteratee.Core.IterateeBuilder.Combine
val comp1 : Iteratee<'c,unit>
val comp2 : Iteratee<'c,'d>
member IterateeBuilder.Delay : f:(unit -> Iteratee<'a,'b>) -> Iteratee<'a,'b>

Full name: FSharp.Monad.Iteratee.Core.IterateeBuilder.Delay
val f : (unit -> Iteratee<'a,'b>)
val iteratee : IterateeBuilder

Full name: FSharp.Monad.Iteratee.Core.iteratee
val enumEOF : _arg1:Iteratee<'a,'b> -> Iteratee<'c,'b>

Full name: FSharp.Monad.Iteratee.Core.enumEOF
val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
val i : Iteratee<'a,'b>
val run : i:Iteratee<'a,'b> -> Choice<exn,'b>

Full name: FSharp.Monad.Iteratee.Core.run
union case Choice.Choice1Of2: 'T1 -> Choice<'T1,'T2>
union case Choice.Choice2Of2: 'T2 -> Choice<'T1,'T2>
val run_ : i:Iteratee<'a,'b> -> Choice<exn,'b>

Full name: FSharp.Monad.Iteratee.Core.run_
val raise : exn:System.Exception -> 'T

Full name: Microsoft.FSharp.Core.Operators.raise
val x : Choice<exn,'b>
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
union case Option.Some: Value: 'T -> Option<'T>
union case Option.None: Option<'T>
Multiple items
val char : value:'T -> char (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.char

--------------------
type char = System.Char

Full name: Microsoft.FSharp.Core.char
type bool = System.Boolean

Full name: Microsoft.FSharp.Core.bool
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val ofSeq : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.List.ofSeq
module String

from Microsoft.FSharp.Core
module Array

from Microsoft.FSharp.Collections
val ofList : list:'T list -> 'T []

Full name: Microsoft.FSharp.Collections.Array.ofList
val rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev
val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map

More information

Link:http://fssnip.net/6g
Posted:13 years ago
Author:Ryan Riley
Tags: iteratee , enumerator , lazy , i/o