Language showdown: Lazy (aka short-circuit) evaluation for And and Or applied to a list.

Question

If I have a boolean function f(x) = {print(x); return is_even(x)} that does some time-consuming (in this example, for illustrative purposes, side-effect-producing) stuff and a list a={2,3,4} I can check if f() is true for every element of a with

apply(And, map(f, a))

but that wastefully applies f to every element of a instead of returning False after the second element. This does the right thing

And(f(2), f(3), f(4))

but of course I want to dynamically create the list. Lisp solves this problem with the built-in "every" function (and similarly for "some") [originally I called them macros]. How do you do it in other languages? Eg,

every(f, a)

should return False without evaluating f(4). (And similarly for some.)

Answer 1

In a lazy language, it probably just works automagically.

In an eager language, you either have to combine the 'map f' part into the 'every' function, or introduce some form of laziness. Below is some F# code that demonstrates both strategies. The first way shows using (eager) lists, where 'Every' takes the function-to-map as an argument. The second way shows using (lazy) IEnumerables, so SeqEvery can just take a seq<bool> and only evaluate as much of it as it needs.

#light

let foo x =
    printfn "%d" x
    x % 2 = 0

// using lists
let rec Every f l =
    match l with
    | [] -> true
    | h::t -> if f h then Every f t else false

let r = Every foo [2;3;4]
printfn "%A" r
//2
//3
//false

// using sequences (which F# calls 'seq', just means IEnumerable)
let rec SeqEvery (s : seq<bool>) =
    let e = s.GetEnumerator()
    let mutable r = true
    while r && e.MoveNext() do
        r <- e.Current
    r

// since they're lazier, we can call map first
let z = [2;3;4] |> Seq.map foo |> SeqEvery
printfn "%A" z
//2
//3
//false

Answer 2

.NET features the linq extension method All, which seem to be what you want. In C#, you would write:

a.All(n => f(n))

or, if f is of type Func<T, bool>:

a.All(f)

Answer 3

In Scheme (R6RS):

(for-all even? '(2 4 6 7))

Answer 4

In common lisp, you have exactly this facility

(every #'f '(2 3 4))

and similarly for some, notevery, notany

the iteration macro loop provides similar short circuiting conveniently, you could get the equivalent effect from

(loop for x in '(2 3 4) always (f x))

which is cumbersome here, but in a more complicated situation may be clearer.

Answer 5

In a functional language, you can use reduce/fold. O'Caml, for example:

let every f = List.fold_left (fun acc x -> acc && f x) true;;

Answer 6

Perl6

sub is_even($n){ !($n %2) }

sub f($n){
  say $n;
  return is_even($n)
}

sub every(&f,@a){
  return 0 unless f($_) for @a;
  return 1;
}

my @a=qw"2 4 0 6 3 2 1";
say "returned: ", every(&f,@a) ?? "True" !! "False"

Outputs:

2
4
0
6
3
returned: False

Answer 7

To explain what Brian meant by "In a lazy language, it probably just works automagically", a simpler Haskell example without side-effects (since you allowed "time-consuming" too): ["And" and "Or" are called "all" and "any"]

Prelude> all even [2,4,6,7, sum [1..1000001]]
False
Prelude> all even [2,4,6,8, sum [1..1000001]]
*** Exception: stack overflow

Or, if you want to see a complete program:

import CPUTime
main = do
     a <- getCPUTime
     print $ all even [2,4,6,7, length [1..100000001]]
     b <- getCPUTime
     print (b-a)

     c <- getCPUTime
     print $ all even [2,4,6,8, length [1..100000001]]
     d <- getCPUTime
     print (d-c)

And running it:

/tmp$ runhaskell test.hs
False
756000000
False
2980243000000

[Note in case the large numbers give the wrong impression: those times are in picoseconds, so it actually means 0.000756 seconds and 2.98 seconds respectively :-)]

Answer 8

in ocaml:

Lists.forall(f, a)

in python:

all(f(x) for x in a)

in prolog (maybe it's not 100% correct, it's been a long time since my last real line of prolog):

all (P, [X|T]):- P(X), all(T).

in brief, usually there's a "test predicate for all" that evaluates in short circuit, if not, just make yours in the ol'good imperative style:

void all(int[N] l, int(*f)(int)) {
  for (int i = 0; i < N; i++) {
    if (!f(l[i])) return;
  }
}

or in the cooler style:

void all(int[N] l, int(*f)(int)) {
  int i = 0;
  while(f(l[i++]) && i < N);
}

Answer 9

Mozart/Oz:

{All [2 4 6 8 9 10] IsEven}  // -> false

{Some [2 4 6 8 9 10] IsOdd}  // -> true

Answer 10

This one is in Scheme using call-with-current-continuation. It should work on any R5RS compatible system.

    (define (f x)
      (begin (display x)
             (even? x)))

    (define (every? f a)
      (call-with-current-continuation
       (lambda (exit)
         (for-each (lambda (i)
                     (if (not (f i)) (exit #f)))
                   a)
         #t)))

Not as short as the R6RS solution.

Answer 11

In ruby:

>> def even?(x) 
>>   puts x; return x % 2 == 0
>> end

>> [6,5,4].all? {|i| even?(i)}
6
5
=> false

Answer 12

Clojure.

With every? of coarse. But that's not really fair, almost everything is lazy by default in Clojure.

(defn even 
  [n] (do 
        (println n) 
        (even? n)))

(every? even [2 3 4])

Output (at the REPL):

|2
|3
false

Stdout marked with | for example purposes. The false is the return value of every?.