Help me extend a function

[GnuVince]

Hey guys, I've got this function which calculates the sum of a given integer list:


let rec sum_int_list = function
[] -> 0
| h::t -> h + (sum_int_list t);;


Now, this works with one dimension lists. Is there a way (an algorithm) to get the sum of all numbers in the list, even if these integers are in a "sublist"? For example:


# sum_int_list [1;2;3];;
- : int = 6
# sum_int_list [[1;2];[3;4]];;
This expression has type 'a list but is here used with type int


This is what I have right now. Would it be possible that if instead of type error on the second example, it calculates 10?

Thanks.

[jemfinch]

You can use List.flatten before calling your sum_int_list function.

Btw, your sum_int_list function is really just a simple fold.

List.fold_left (fun i acc -> i + acc) 0


If you want to write the function itself without using List.flatten, you'll just want to double that.

List.fold_left (fun l acc -> acc + (List.fold_left (fun i acc -> i + acc) 0 l)) 0


I've just discovered the list folding functions myself, but in SML. They really make most iterative concepts easy to implement. I remember days when I would've even used a reference to implement something like the above.

Btw, your function isn't tail recursive. If you don't want to use a folding function, this is the way you should write your function:


let sum_int_list =
let helper acc l =
match l with
| [] -> acc
| hd :: tl -> helper (acc + hd) tl
in
helper 0


Jeremy

[GnuVince]

Ah nice, very cute. Thanks Jeremy. Also it seems your O'Caml skills are diminishing, you forgot your 'rec' keyword in your helper function ;)

[jemfinch]

As a note, there's something strange about that function (the second example above) that won't let O'Caml typecheck it. I can't figure it out, maybe PrBacterio or someone can. Here's the SML version that typechecks perfectly fine to (int list list -> int):


List.foldl (fn (l, acc) => acc + (List.foldl (fn (i, acc) => i + acc) 0 l)) 0


Jeremy

[jemfinch]

Originally posted by GnuVince
Ah nice, very cute. Thanks Jeremy. Also it seems your O'Caml skills are diminishing, you forgot your 'rec' keyword in your helper function ;)

Oh, well poo on O'Caml! SML doesn't require "rec" :)

Yeah, it's kind of hard converting between the two because they're so close in both syntax and semantics. Between the two, though, I definitely prefer SML.

Jeremy

[GnuVince]

s/definition/definitly maybe? Man you need some sleep :)

[jemfinch]

Yeah, it's finals week here. Can you tell? :)

Just had my Latin final this morning, tomorrow I have Chemistry final, and Wednesday I have both my Greek and my Math finals.

Jeremy

[GnuVince]

Not nearly as bad as me: COBOL exam last Friday, this Thursday and next Thursday!

[jemfinch]

COBOL is cake compared to Greek :)

[GnuVince]

It doesn't take 4 pages of greek to say "4". Our first program in COBOL did. :p

[jemfinch]

On the other hand, I can't even write Greek here to show you what it looks like :)

Jeremy

[PrBacterio]

Originally posted by jemfinch
As a note, there's something strange about that function (the second example above) that won't let O'Caml typecheck it. I can't figure it out, maybe PrBacterio or someone can. Here's the SML version that typechecks perfectly fine to (int list list -> int)

You mixed up the order of the arguments. For some strange reason, in the SML version of fold, the accumulator seems to come as the second argument to the folded function, even though it is the first argument of the function returned by fold.

This version should work:
List.fold_left (fun acc l -> acc + (List.fold_left (fun acc i -> i + acc) 0 l)) 0
Oh and GnuVince, to answer your question more generally: What you actually want to do is generalize your sum_list function so it can also 'sum' other objects, not only lists. So you would write it, then, as taking, besides the list of the objects to sum, the addition function, i.e. '+', and an initial zero element; something like:
let rec generalized_sum sum_fun zero = function
[] -> zero
| hd :: tl -> generalized_sum sum_fun (sum_fun zero hd) tl

This could then be used like:
# generalized_sum ( + ) 0 [1;2;3];;
- : int = 6
# generalized_sum ( +. ) 0.0 [1.0;2.0;3.0];;
- : float = 6
# generalized_sum (fun acc -> generalized_sum ( + ) acc) 0 [[1;2;3];[4;5;6]];;
- : int = 21
Now we can see from these examples that, in writing this generalized list summing function, generalized_sum, what we have actually done is to reinvent the fold_left function from the standard library - because this is just what that function does: It 'adds' the elements of a list in a generalized way, being given an addition operation and a zero element to start with as arguments.

Thus, starting from your simple problem, by generalizing it we have arrived at the general fold function - only out of generalizing this simply problem we have arrived at the exact same, general folding function!
On the other hand, I can't even write Greek here to show you what it looks like

Jeremy
In fact, it IS possible to use greek or japanese or whatever here; most modern ubb systems should not have any trouble whatsoever with unicode input. Example: Ελλάδα (only works with the right page-encoding settings / fonts installed; note also that I dont have the slightest idea about the greek language so I probably botched that :] )

[jemfinch]

Originally posted by PrBacterio

You mixed up the order of the arguments. For some strange reason, in the SML version of fold, the accumulator seems to come as the second argument to the folded function, even though it is the first argument of the function returned by fold.


I think, really, that O'Caml has it a bit backwards from the way I normally think.

First, the arguments to List.foldl are in the natural order for currying: first the higher order function, then the initial state for the accumulator, and then the list to be processed. I'm sure you'll agree that that's the most natural order for foldl to have.

In SML, the function taken by foldl is this:

type element
type accumulator

element * accumulator -> accumulator

In O'Caml, it's this:

accumulator -> element -> accumulator

I can't speak for which is more natural for people other than myself, but I find the SML ordering (and tupling) more natural than the O'Caml ordering (and currying). When I write functions that accumulate in their arguments (like the "helper" function I wrote above for GnuVince) I always put the actual argument first, and the accumulator last. This is the order SML uses, and opposite the order O'Caml chooses. Also, it doesn't make any sense to partially apply the function given to foldl, so SML uses a tuple instead of arguments that can possibly be curried (though this is really much more of a design difference between SML and O'Caml).


In fact, it IS possible to use greek or japanese or whatever here; most modern ubb systems should not have any trouble whatsoever with unicode input. Example: Ελλάδα (only works with the right page-encoding settings / fonts installed; note also that I dont have the slightest idea about the greek language so I probably botched that :] )

Yeah, I know ubb systems have the capability, but I wasn't talking about UBB lacking capability, I was talking about me lacking capability :p I have no idea how to input Greek so I can show GnuVince what it looks like :)

That wasn't Greek that you showed, btw :)

Jeremy

[PrBacterio]

Originally posted by jemfinch
That wasn't Greek that you showed, btw :)

Well I entered it as greek letters. I dont know if it is valid greeek though ... but if you dont select the correct page encoding in your browser it will only show as rubbish anyway. Encoding -> UTF8 and it should at least show it as valid greek characters, though as I said I dont know if its even a valid word (its supposed to spell out the word for greece but as I said I have no idea about the language).

Oh and I find OCaml's ordering more natural/convenient simply for the reason that in OCaml, the folding function gets its arguments in the same order as the folded function (and thus can, by partial application, again, itself, be used as a function to be folded).

Notice that because of this the solution you posted:
List.fold_left (fun acc l -> acc + (List.fold_left (fun acc i -> i + acc) 0 l)) 0
can be formulated in a more concise fashion like this:
List.fold_left (List.fold_left ( + )) 0
which would not be possible with SML-styles ordering or tupling of arguments.

[jemfinch]

Ah, how'd you type those Greek characters in?

Jeremy

[PrBacterio]

Originally posted by jemfinch
Ah, how'd you type those Greek characters in?

Jeremy

With help of the wonders of the Microsoft IME :)