Rich February 2016

Multiple input types with fold

I am trying to figure out how to implement the fold functions on inputs of differing types. As a sample, I'll use the count function for a list (though, I have multiple functions to implement for this). Assuming an int list input (this should work with any type of list, though), my count function would be

val count = foldr (fn(x:int,y)=>y+1) 0 ;
val count = fn : int list -> int

However, I am attempting to make a count function where the type is

val count = fn : int list * bool list -> int

where the int list is the universe of the set, and the bool determines which values of the universe are in the set. ie, (1,3,5,6),(true,false,false,true) results in a final set of (1,6), which would have a count of 2. My first thought to try this was some form of

val count= foldr (fn(x:(int*bool),y)=>if #2x then y+1 else y ) 0 ;

but this results in a return type of

val count = fn : (int * bool) list -> int

which is not quite what I need. Logically, they are similar, but I am expected to group the two types together in one list each.

Answers


Simon Shine February 2016

  1. You could use ListPair.foldl:

    fun count (xs, bs) = ListPair.foldl (fn (x, b, acc) => ...) ... (xs, bs)
    

    where the first ... is some combination of x, b and acc and the second ... is the initial value.

    This assumes that xs and bs are equally long, and in case they're not, discards the remaining elements in the longer list. (You should probably try to justify if this gives the correct answer in either case xs or bs is longer.)

  2. Otherwise, you need to combine (aka zip) your int list × bool list into an (int × bool) list by making a function that combines two lists, and use this function in combination with the folding you are already doing.

    fun combine (x::xs, y::ys) = ...
      | combine (..., ...) = ...
    

    This function could be equivalent to ListPair.zip.

Post Status

Asked in February 2016
Viewed 1,446 times
Voted 12
Answered 1 times

Search




Leave an answer