CODEWITHSUNDEEP
functional-programmingsmlfoldml
Jéssica Carneiro
Jéssica Carneiro

Reputation: 167

foldr/foldl with logic operators in SML

I'm trying to build a function in SML using foldr or foldl that will return the logic or and logic and of all elements in a list.

I've tried in this way, using and and or:

fun band x = foldr (op and) true x;
fun bor x = foldr (op or) false x;

And also using andalso and orelse. But I keep receiving error messages such as:

Error: unbound variable or constructor: or

Upvotes: 4

Views: 2440

Answers (3)

sshine
sshine

Reputation: 16145

(Answer instead of comment.) Consider using List.all : ('a -> bool) -> 'a list -> bool and List.exists : ('a -> bool) -> 'a list -> bool since they're short-circuiting, unlike List.foldl. There is really no point in folding farther than the first false in band's case, or true in bor's case. That is,

val band = List.all (fn b => b)
val bor = List.exists (fn b => b)

One definition for these library functions is found here:

fun all p []      = true
  | all p (x::xr) = p x andalso all p xr;

fun exists p []      = false
  | exists p (x::xr) = p x orelse exists p xr;

Since the list being fed to band and bor are already of type bool, passing the identity function (fn b => b) will produce the desired truth value. The functions are generic enough to work on any kind of list for which you can apply a predicate for each element, so if you were generating your bool list from some other list, you could avoid that step.

Upvotes: 4

newacct
newacct

Reputation: 122538

There are no operators called and and or in SML. and is a keyword to separate multiple variable or declarations that are declared at the same time. There is no or.

The AND and OR logical operators are andalso and orelse which as you said in your own answer are short-circuiting, and not regular operators.

Upvotes: 3

Jéssica Carneiro
Jéssica Carneiro

Reputation: 167

I've found out the problem: andalso and orelse are not operators nor functions cause they implement a short-circuit evaluation.

Therefore, the solution should be:

fun band x = foldl (fn (a,b) => a andalso b) true x;
fun bor x = foldr (fn (a,b) => a orelse b) false x;

Upvotes: 4

Related Questions