Using foldr to simplify a function (SML / NJ)

Question

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?

Answer 1

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