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 &#91;&#93;)
      else
         List.rev (step_aux start (~inc) fin f &#91;&#93;)
  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.

Advertisements

~ by hellfeuer on June 12, 2008.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: