CODEWITHSUNDEEP
functional-programmingsmlsmlnjfold
user2796815
user2796815

Reputation: 465

Using foldr to simplify a function (SML / NJ)

I have this function 

fun exist p M = foldr( fn(x,y) => x orelse y ) false (map p M)

I need to write it using only the foldr function, but can only call foldr once. I'm confused on how I should handle this. Do i need to revise my anon function?

Upvotes: 0

Views: 3033

Answers (1)

zaquest
zaquest

Reputation: 2050

Yes, you need to revise your anonymous function. You can call p inside it.

fun exist p M = foldr (fn (x, y) => y orelse (p x)) false M

map in your code transforms values to bool type. You can do that in anonymous function. Also, switching x and y in orelse will save you some machine time, since if value satisfying p was found, p won't be executed on the rest of M.

- fun exist p M = foldr (fn (x, y) => y orelse (p x)) false M;
val exist = fn : ('a -> bool) -> 'a list -> bool
- exist (fn e => e = 1) [2,3,4];
val it = false : bool
- exist (fn e => e = 1) [2,3,4,1,2,3,4];
val it = true : bool

foldr takes 3 arguments

  1. function to fold list. It takes tuple argument (x, y), where x is current value from list, y - value list have been folded to so far.
  2. Starting value. It will be passed as y to the first first argument function together with the last value of a list.
  3. List to fold. Each value (starting last) of this list will be passed to the first argument function as x.

foldr will call folding function for every element of passed list.

Calls to folding (called it anon here) function for exist (fn e => e = 1) [2,1,4]; call:

anon (4, false);                              // here `false` is the false passed to `foldr`; returns false
anon (1, false orelse (p 4));                 // (p 1) -> true; returns true
anon (2, (false orelse (p 4)) orelse (p 1));  // returns true becuase `true or (p 2)` is true

Upvotes: 3

Related Questions