0

How can i find the sum of elements of a linked list using a function in F#?

John Oriely
  • 43
  • 1
  • 6

4 Answers4

10

F# has a built-in 'linked list' (generic) type - that is just called list, and that already has a function to compute the sum:

let list1 = [2; 3; 5]
List.sum list1

Arbitrary operations on lists can be written using recursive function:

let rec sum l = 
  match l with
    | [] -> 0
    | head::tail -> head + (sum tail)

but in most cases it is enough to use the built-in fold function:

let sum l =
  List.fold (fun total element -> total + element) 0 l

Note also that the above 'naïve' recursive function is not tail-recursive, and so it will crash when applied to very long lists. The tail-recursive implementation would be something like this:

let sum l =
  let rec sumAcc acc l = 
    match l with
      | [] -> acc
      | head::tail -> sumAcc (acc+head) tail
  sumAcc 0 l

that is basically what fold does.

(I am adding this answer in case someone that does not know F# lands on this page - he/she could get a mistaken idea about lists support in F#)

Community
  • 1
  • 1
MiMo
  • 11,793
  • 1
  • 33
  • 48
1
let rec sum a = 
    match a with
    |Nil -> 0
    |Link(s,t) -> s+(sum (!t))
Jean-Bernard Pellerin
  • 12,556
  • 10
  • 57
  • 79
1

I tried your example, it doesn't work, so I did fix it.

type lists = Nil | Link of (int * (lists ref))

let list1 = Link(3, ref (Link (2, ref Nil)))
let list2 = Link(6, ref (Link (4, ref Nil)))
let list3 = Link(9, ref (Link (6, ref Nil)))

let rec sum = function      // or  let rec sum list = match list with
    | Nil              -> 0
    | Link(head, tail) -> head + sum !tail

You don't need to define Integer of int , if you do it, you'll have to tag all numbers with Integer

Gus
  • 25,839
  • 2
  • 51
  • 76
  • hmm interesting, when I try this, it says the 'h' and 'sum !t' types do not match each other – John Oriely Apr 29 '13 at 22:49
  • It works for me. Are you sure? Try the code from scratch, I just renamed some variables. – Gus Apr 29 '13 at 22:51
  • ah I typed the line incorrectly when I declared. type rNumber = Integer of int;; type lists = Nil | Link of (rNumber * (lists ref));; it's suppose to be "rNumber" not Integer. That's why I'm getting an error stating the type 'int' does not match 'rNumber'. How would I get around this? thanks for your help so far! – John Oriely Apr 29 '13 at 23:01
  • If you do it that way, you'll have to write the values like: let list1 = Link(Integer 3, ref (Link (Integer 2, ref Nil))) but I think it doesn't help to have to prefix all numbers with Integer. – Gus Apr 29 '13 at 23:03
  • Hi @JohnOriely if this or any answer has solved your question please consider [accepting it](http://meta.stackexchange.com/q/5234/179419) by clicking the check-mark. This indicates to the wider community that you've found a solution and gives some reputation to both the answerer and yourself. There is no obligation to do this. – Gus Jun 10 '14 at 22:06
1

Just for sake of completeness:

let sum l =
   l 
   |> List.reduce (+)

will also do the trick. Type inference will infer l to be an int list so if you need some other numeric type you can do this (for example a list of longs):

let sum (l:list<int64>) =
   l 
   |> List.reduce (+)

or this:

   let inline sum l =
      l
      |> List.reduce (+)

The inline will generalize the sum function to work on any type that provides a static function named "+". To use it, you'd have code like this:

let mylist = [1;2;3;4]
let sumOfMyList = sum mylist;;

I would also say that in my experience, using list folds and related functions is a better approach than rolling your own recursive functions.

Onorio Catenacci
  • 14,928
  • 14
  • 81
  • 132