How to add all elements in a list in SML

Question

I am trying to add all elements in a given integer list and finally return an integer as its sum

Following is the code I have tried

val intList = [1,2,3,4];

fun addList (list) = 
let
  val head = List.hd list
  val tail = List.tl list
  val sum = ref 0
in
  if(list <> [])
  then sum := !sum + head
  addList(tail)
  else !sum
end;

However, I am getting the following error

Elaboration failed: Type clash. An expression of type "'a" cannot have type "(('a → 'b) → 'c → 'd) List.list" because of circularity.

I am quite new to SML/NJ What could I be doing wrong?

Answer 1

So, I was looking into a different problem and I found a solution for this one as well.

val intList = [3,7,5,6];

fun addList (list, x)=
if list = []
then x
else
let
  val head = hd(list)
in
  addList(tl(list), x + head)
end;


val something = addList(intList, 0);

It is similar to how the foldl operation works, but ofcourse different in terms of use.

I didn't know we could pass an element this way as an argument to the function. This was interesting.

Answer 2

You're far along the wrong track - you shouldn't even be thinking about references or assignments.
(In fact, you're probably never going to use them.)

Here is the general idea - it is very straightforward to translate into SML:

The sum of a list is

• If the list is empty, it is zero
• Otherwise, add the head of the list to the sum of the tail of the list.

Note that there are no variables and no assignments anywhere.

Answer 3

Ideally, you should reduce the entire list into single element using binary operation. In Standard ML you can do this using List.foldl function.

> val sum = List.foldl op+ 0 [1, 2, 3, 4];
val sum = 10: int

This essentially puts + between consecutive elements and evaluates to

> val sum = (((0 + 1) + 2) + 3) + 4;

op+ is a way to pass an operator to a function. https://stackoverflow.com/a/54814038/5956245

https://smlfamily.github.io/Basis/list.html#SIG:LIST.foldl:VAL

Answer 4

To answer the comment asking about using List.hd and List.tl before checking whether list is empty, this can result in an exception, and because the recursion converges on the empty list case, will result in an exception. We need to do this after that check. Fortunately let ... in ... end is an expression and can be used anywhere an expression is expected. So now:

fun addList(list) = 
  if list <> [] then
    let
      val head = List.hd list 
      val tail = List.tl list
      val sum = ref 0
    in
      sum := !sum + head;
      addList(tail)
    end
  else 
    !sum;

Now we don't have sum bound in the else branch. This gives us a compilation error. So, let's modify this again.

fun addList(list) = 
  let
    val sum = ref 0
  in
    if list <> [] then
      let
        val head = List.hd list 
        val tail = List.tl list
      in
        sum := !sum + head;
        addList(tail)
      end
    else 
      !sum
  end;

But the problem here is that sum is bound to a different reference to 0 on each recursive function call. Calling addList on any list will yield 0. We would need a recursive function which operates on the same sum reference by binding that name in an outer scope which an inner function will enclose.

fun addList(list) = 
  let
    val sum = ref 0

    fun aux(list) =
      if list <> [] then
        let
          val head = List.hd list 
          val tail = List.tl list
        in
          sum := !sum + head;
          aux(tail)
        end
      else 
        !sum
  in
    aux(list)
  end;

Of course, what if we don't use List.hd and List.tl at all but substitute pattern-matching, which is much more idiomatic.

fun addList(list) = 
  let
    val sum = ref 0

    fun aux(list) = 
      case list of
          [] => !sum
        | head::tail => (
            sum := !sum + head;
            aux(tail)
          )
  in
    aux(list)
  end;

Or more concisely:

fun addList(list) = 
  let
    val sum = ref 0

    fun aux([]) = !sum
      | aux(head::tail) = (
          sum := !sum + head;
          aux(tail)
        )
  in
    aux(list)
  end;

Of course the proper way to write this is to avoid the use of ref entirely, as mutable state is non-idiomatic in this situation, and entirely unnecessary. The use of a fold, as already suggested handily avoids tail-recursion and means that no matter how large a list we sum, we'll never encounter a stack overflow.