ChurchLists in F#

church_list.fs

type [<AbstractClass>] ChurchList<'T>() =
  class
    abstract RunList: ('T -> 'S -> 'S) -> 'S -> 'S
  end

module ChurchList =
  module Details =
    let inline adapt    f       = OptimizedClosures.FSharpFunc<_, _, _>.Adapt f
    let inline invoke   f v s   = (f : OptimizedClosures.FSharpFunc<_, _, _>).Invoke (v, s)

    let inline runList (cl : ChurchList<_>) f z = cl.RunList f z

    module Loops =
      let rec ofRange f s e i =
        if i < e then
          ofRange f (invoke f i s) e (i + 1)
        else
          s
  open Details

  // Sources

  let empty () : ChurchList<'T> =
    { new ChurchList<'T>() with
        member x.RunList f z = z
    }

  let inline singleton v  = 
    { new ChurchList<'T>() with
        member x.RunList f z = f v z
    }

  let inline ofArray l  =
    { new ChurchList<'T>() with
        member x.RunList f z = Array.foldBack f l z
    }

  let inline ofList l  =
    { new ChurchList<'T>() with
        member x.RunList f z = List.foldBack f l z
    }

  let inline ofRange b e =
    { new ChurchList<int>() with
        member x.RunList f z = Loops.ofRange (adapt f) z e b
    }

  // Sinks
  let inline toList vs = runList vs (fun v s -> v::s) []

  let inline toArray vs = 
    let ra = ResizeArray 16
    runList vs (fun v s -> ra.Add v; s) ()
    ra.ToArray ()

  let inline sum vs = runList vs (+) LanguagePrimitives.GenericZero

  // Pipes

  let inline collect m vs = 
    { new ChurchList<'T>() with
        member x.RunList f z = 
          runList vs (fun v s -> runList (m v) f s) z
    }

  let inline filter m vs = 
    { new ChurchList<'T>() with
        member x.RunList f z = 
          let f = adapt f
          runList vs (fun v s -> if m v then invoke f v s else s) z
    }

  let inline map m vs = 
    { new ChurchList<'T>() with
        member x.RunList f z = 
          let f = adapt f
          runList vs (fun v s -> invoke f (m v) s) z
    }

  let inline sortBy m vs = 
    { new ChurchList<'T>() with
        member x.RunList f z = 
          let avs = vs |> toArray 
          Array.sortInPlaceBy m avs
          runList (ofArray avs) f z
    }

  // Misc
  let inline cons v vs = 
    { new ChurchList<'T>() with
        member x.RunList f z = f v (runList vs f z)
    }

  let inline snoc vs v = 
    { new ChurchList<'T>() with
        member x.RunList f z = runList vs f (f v z)
    }

  let inline append vs ws = 
    { new ChurchList<'T>() with
        member x.RunList f z = runList vs f (runList ws f z)
    }

  let inline zip l =
    { new ChurchList<_> () with
        override x.RunList r z =
          let r = adapt r
          let ss = runList l (fun (s, i) v -> (invoke r s (v, i), i + 1)) (z, 0)
          fst ss
    }

  let inline take n l =
    { new ChurchList<_> () with
        override x.RunList r z =
          let r = adapt r
          let ss = runList l (fun (s, i) v -> if i < n then (invoke r s v, i + 1) else (s, i + 1)) (z, 0)
          fst ss
    }

  let inline skip n l =
    { new ChurchList<_> () with
        override x.RunList r z =
          let r = adapt r
          let ss = runList l (fun (s, i) v -> if not (i < n) then (invoke r s v, i + 1) else (s, i)) (z, 0)
          fst ss
    }


[<EntryPoint>]
let main argv = 
  0