## Extending SML’s lists

I’ve been busy working on a project in SML/NJ, and in the process I ended up writing a few generic list functions. I’ve extracted these into a separate module, and I’m putting it up here. Warning: These are just quick hacks (but they work (I think!)), and not all of them will be useful outside of my project.

Briefly, here’s what this contains:

A specialized version of foldl, a join function similair to Ruby’s, list generating functions and range functions, map and app functions that also pass in the index of the element, and a special kind of cross product function.

Anyway here goes (sorry for the meaningless syntax highlighting, SML/NJ is of course not supported by the WordPress sourcecode plugin):

structure ListExtension = struct exception InvalidArgument of string; (* * folds left across a list, applying a binary function pairwise to its members. * Eg, foldLeft f [a,b,c] = f(f(a,b),c); *) fun foldLeft f [] = raise InvalidArgument "Empty list to foldLeft" |foldLeft f (h::[]) = h |foldLeft f (h::t) = foldl (fn (a,b) => f (b,a)) h t (* * 'joins' a list into a string, converting each member into a string by the * given function, and interspersing the given string *) local fun join_aux s f (h::t) res = if res = "" then join_aux s f t (f h) else join_aux s f t (res ^ s ^ (f h)) |join_aux s f [] res = res in fun join s f h = join_aux s f h "" end (* * Convenience function when the conversion is identity * eg joinString "+" ["a", "b", "c"] = "a+b+c" *) fun joinString s h = join s (fn a => a) h (* * List generators. *) local fun step_aux n inc lim f l = if (inc > 0 andalso n > lim) orelse (inc < 0 andalso n < lim) orelse (inc = 0) then l else step_aux (n + inc) inc lim f ((f n)::l) in fun step start fin inc f = if start <= fin then List.rev (step_aux start inc fin f []) else List.rev (step_aux start (~inc) fin f []) end fun downfrom n f = step n 0 1 f fun upto n f = step 0 n 1 f fun fromto start fin f = step start fin 1 f fun range from to = ste from to 1 (fn i => i) fun rangeStep from to inc = step from to inc (fn i => i) (* * Map with index. Same as List.map, but also passes in the index as an * argument to the given function *) local fun mapi_aux f [] i res = (List.rev res) |mapi_aux f (h::t) i res = mapi_aux f t (i+1) (f (i,h)::res) in fun mapi f l = mapi_aux f l 0 [] end (* * app with index. Same as List.app, but also passes in the index as an * argument to the given function *) local fun appi_aux f [] i = () |appi_aux f (h::t) i = (f (i, h); appi_aux f t (i+1)) in fun appi f l = appi_aux f l 0 end (* * Applies the function f to each element of the cross product of the two * lists. * f(a,b) is discarded if it is NONE, if it is SOME(c) then c is added to the result *) local fun crossProduct_aux f (h::t) l result = crossProduct_aux f t l ((List.mapPartial (f h) l) @ result) |crossProduct_aux f [] l result = result in fun crossProduct f (a, b) = crossProduct_aux f (List.rev a) b [] end end

Suggestions/ additions are welcome of course.