SML - Alternating Sum Using Pattern Matching

Question

I'm writing a program that accepts a list of int and returns the value of their alternating sum.

Input: [1,2,3,4]
Output: 1 + (-2) + 3 + (-4)

Below is the code I tried to write for doing this, but I keep getting the error syntax error: inserting ORELSE

My if then else statement looks correct, so I'm not sure what could be causing the error

fun alternate([]) = 0
  | alternate(x::xs, count) = 
        count = count + 1
        if count mod 2 == 0 then (~x) + alternate(xs)
        else x + alternate(xs)

Answer 1

I do not see a mention in any answer that tracking this count is wholly unnecessary with the key term pattern-matching in the title. We can match on more than just the first element and tail of a list.

• For an empty list, the answer is 0.
• For a list with a single element, the answer is that single element.
• For a list with at least two elements, we subtract the second from the first and add the result of recursively calling alternate on the tail.

fun alternate([]) = 0
  | alternate([x]) = x
  | alternate(a::b::tl) = a - b + alternate(tl);

Alternatively, we can break this down.

• A function which maps different functions onto alternating members of a list and generates a new list.
• A sum function which leverages a left fold.
• And then just put those two together.

fun map2 _ _ [] = []
  | map2 f _ [x] = [f x]
  | map2 f g (x::y::tl) = f x :: g y :: map2 f g tl;

fun sum lst = foldl op+ 0 lst;

sum (map2 (fn x => x) (fn x => ~x) [1, 2, 4, 5, 7]);

Answer 2

altsum n = x1 -x2 +x3 -x4 +... +xn
      = x1 -(x2 -x3 +x4 +...+xn)
      = x1 - altsum(n-1)

fun altsum [] = 0
  | altsum x::xs = x - altsum xs`

Answer 3

Here alternative solution

altSum :: (Num a) => [a] -> a
altSum (x:[]) = x
altSum (x:y:xs) = x - y + altSum xs

Answer 4

Building on my previous answer I would suggest implementing sum:

val sum = foldr (op +) 0;

Copying the alternate function from that answer here for completeness, with a small bugfix:

fun alternate l =
   let
       fun alternate1 []      = []
         | alternate1 (x::xs) =   x  :: alternate2 xs
       and alternate2 []      = []
         | alternate2 (x::xs) = (~x) :: alternate1 xs
   in
       alternate1 l
   end

Then you can define alternate_sum quite simply:

val alternate_sum = sum o alternate

There will of course be objections in the name of performance. Haskell is able to perform deforestation/fusion optimizations across these sorts of invocations because it knows something about the purity of the functions; Standard ML does not require these optimizations though some implementations may attempt them, I don't know.

The overhead on this particular problem may or may not be absurd, but I think it's a good example of functional programming principles regardless: building up complex behavior from simpler, unimpeachable behavior. The "burden of proof" in this version is almost all on alternate. @SunsetRider's version is fine (it will probably perform better) but the code is more "monolithic" you might say.

Also, @SunsetRider's code is a little more complex than it needs to be, this version is sufficient:

fun alternate l =
  let 
    fun alt([], count) = 0
      | alt(x::xs, count) =
          if count mod 2 = 0 then x + alt(xs, count+1)
          else (~x) + alt(xs, count+1)
  in 
    alt(l, 0)
  end

One comment in addition to what @SunsetRider said: in general, in functional languages x = x + 1 and other mutations are a bit of a code smell. You can see that in their code they use count+1 several times instead. Thinking functionally, what matters is what expressions are evaluating to, not the state of variables, so the values that are passed around are critical. This goes back to the superb definition at the beginning of the excellent and hugely underrated book Functional C by Pieter Hartel:

The functional and imperative paradigms operate from different viewpoints. The functional paradigm is based on the evaluation of expressions and binding variables to values. The basic program phrase is the expression, the purpose of evaluating an expression is to produce a value. The order in which subexpressions are evaluated does not affect the resulting value.

The imperative paradigm is based on the execution of statements and having a store where the statements can leave their results. The basic program phrase is the statement; the purpose of executing a statement is to change the store. The order in which statements are executed does affect the resulting values in the store. The current set of values in the store is referred to as the state of the program.

Answer 5

This error is caused by that count = count + 1 and if ... else ... are multiple expressions. If you want to execute multiple expressions, you can write the code like this:

(expression1;
 expression2;
     ...
 expressionN);

There are two other errors in your code.
1. The parameters are not the same type in different pattern clauses of the function alternate.
2. In SML = indicates equality, not ==.

So a correct solution may look like this:

fun alternate([]) = 0
  | alternate(x::xs) =
      let 
        fun alt([], count) = 0
          | alt(x::xs, count) =
              if count mod 2 = 0 then x + alt(xs, count+1)
              else (~x) + alt(xs, count+1)
      in 
        alt(x::xs, 0)
      end;