Accumulator generator in F#

Question

In my quest to learn more F#, I tried to implement an "accumulator generator" as described by Paul Graham here. My best solution so far is completely dynamically typed:

open System

let acc (init:obj) : obj->obj=
  let state = ref init
  fun (x:obj) ->
    if (!state).GetType() = typeof<Int32>
       && x.GetType() = typeof<Int32> then
      state := (Convert.ToInt32(!state) + Convert.ToInt32(x)) :> obj
    else
      state := (Convert.ToDouble(!state) + Convert.ToDouble(x)) :> obj
    !state

do
  let x : obj -> obj = acc 1  // the type annotation is necessary here
  (x 5) |> ignore
  printfn "%A" (x 2)   // prints "8"
  printfn "%A" (x 2.3) // prints "10.3"

I have three questions:

• If I remove the type annotation for x, the code fails to compile because the compiler infers type int -> obj for x - although acc is annotated to return an obj->obj. Why is that and can I avoid it?
• Any ideas to improve this dynamically typed version?
• Is it possible to implement this with proper static types? Maybe with member constraints? (It is possible in Haskell, but not in OCaml, AFAIK)

Answer 1

In my quest to learn more F#, I tried to implement an "accumulator generator" as described by Paul Graham here.

This problem requires the existence of an unspecified numeric tower. Lisp happens to have one and it happens to be adequate for Paul Graham's examples because this problem was specifically designed to make Lisp look artificially good.

You can implement a numeric tower in F# either using a union type (like type number = Int of int | Float of float) or by boxing everything. The following solution uses the latter approach:

let add (x: obj) (y: obj) =
  match x, y with
  | (:? int as m), (:? int as n) -> box(m+n)
  | (:? int as n), (:? float as x)
  | (:? float as x), (:? int as n) -> box(x + float n)
  | (:? float as x), (:? float as y) -> box(x + y)
  | _ -> failwith "Run-time type error"

let acc x =
  let x = ref x
  fun (y: obj) ->
    x := add !x y
    !x

let x : obj -> _ = acc(box 1)
do x(box 5)
do acc(box 3)
do printfn "%A" (x(box 2.3))

However, numeric towers are virtually useless in the real world. Unless you are very careful, trying to learn from these kinds of borked challenges will do you more harm than good. You should leave asking yourself why we do not want a numeric tower, do not want to box and do not want run-time type promotion?

Why didn't we just write:

let x = 1
let x = x + 5
ignore(3)
let x = float x + 2.3

We know the type of x at every step. Every number is stored unboxed. We know that this code will never produce a run-time type error...

Answer 2

I agree with Jon that this is quite artificial example and it is not a good starting point for learning F#. However, you can use static member constraints to get reasonably close without dynamic casts and reflection. If you mark it as inline and add convert both of the parameters using float:

let inline acc x = 
  let x = ref (float x)
  fun y ->
    x := (float y) + !x
    !x

You'll get a function with the following type:

val inline acc :
   ^a -> ( ^b -> float)
    when  ^a : (static member op_Explicit :  ^a -> float) and
          ^b : (static member op_Explicit :  ^b -> float)

The function takes any two arguments that can be explicitly converted to float. The only limitation compared to the LISP version (I guess) is that it always returns float (as the most universal numeric type available). You can write something like:

> acc 1 2;;            // For two integers, it returns float
val it : float = 3.0
> acc 1 2.1;;          // integer + float
val it : float = 3.1
> acc 1 "31";;         // It even works with strings!
val it : float = 32.0

Answer 3

It's definitely not possible to implement this with proper static types. You say you can in Haskell, but I don't believe you.

Answer 4

The problem with trying to do this with static typing is in adding two different numbers of possibly different types while preserving the type of the left-hand side. As Jon Harrop says this is possible with a union type. Once you've defined the union type and a corresponding addition operation which works as mentioned, the actual accumulator is very simple. My implementation:

module MyTest

type Numeric =
  | NInt of int
  | NFloat of float

  member this.Add(other : Numeric) : Numeric =
    match this with
      | NInt x ->
        match other with
          | NInt y -> NInt (x + y)
          | NFloat y -> NInt (x + (int y))
      | NFloat x ->
        match other with
          | NInt y -> NFloat (x + (float y))
          | NFloat y -> NFloat (x + y)

  override this.ToString() =
    match this with
      | NInt x -> x.ToString()
      | NFloat x -> x.ToString()

let foo (n : Numeric) =
  let acc = ref n
  fun i ->
    acc := (!acc).Add(i)
    !acc

let f = foo (NFloat 1.1)
(2 |> NInt |> f).ToString() |> printfn "%s"