f# custom linked list and references

Question

i am new to this language. In order to try and understand referencing i have tried implementing a simple directed list the freshman college computer science way.

type item = { 
    value:float 
    next:ref<item>
}

type list() = 
    let head:ref<item> = null // tried instantiation so many different ways and it likes none of em

    let sum i = 
        if i == null then
            0
        else 
            i.value + sum i.next // constructor not defined?

Please tell me why im bad at this

Answer 1

First of all you try to implement it in some imperative way - this is ok, but not really functional. Anyway, the first thing you have problems with is, that you cannot assign null - if you really want to you have to add [<AllowNullLiteral>] to your item type (but of course you have to make it a class instead of a record):

[<AllowNullLiteral>]
type Item(value, next) = 
    member this.value = value
    member this.next : Item ref = next

let head : ref<Item> = ref null

let rec sum (i : Item) = 
    if i = null then
        0.0
    else 
        i.value + sum !i.next

But this is almost never a good idea, so I would start like this:

module List =

   type Item = { value : float; next : List }
   and  List = Item option ref

   let empty : List = ref None
   let single x = { value = x; next = ref None }

   // this is how you can change the list
   let rec append x l =
      let item = single x
      match !l with
      | None -> 
         l := Some item
      | Some node ->
         append x node.next

   let rec sum (l : List) =
      match !l with
      | None      -> 0.0
      | Some item -> item.value + sum item.next

now if you watch closely you will see that you don't really need the refs if you just append at the front and voila ... you got your usual functional list ;)

PS: you forgot some other things too:

• you are using floats in there so you have to use 0.0 instead of 0
• your sum-function has to be recursive (mind you it's not tail-recursive so you will get problems with big lists!)
• you have to dereference ref-cells with !
• you have to construct ref-cells with ref (for example ref null)
• your type list() = made no sense to me so I converted it into a module

PPS: please not that it's not the F#-Way to mutate things like this - it's just to show you how you can do it ... but don't if you don't have to