CODEWITHSUNDEEP
haskellfunctional-programmingocaml
Rhidian
Rhidian

Reputation: 65

Programming style in OCaml

I have a question about the correct way to write efficient functional programs. Suppose I'm given a list s of positive ints, and I want to find the minimum element (or just 0 if empty). Then a generic functional program for doing this would look like

minList s =
    | [] -> undefined
    | [x] -> x
    | x :: t -> min x (minList t)

In a lazy language one can make this more efficient by adding an extra clause which terminates the recursion if a zero is found - this way s is only computed up to the first zero

minList s = 
    | [] -> undefined
    | [x] -> x
    | x :: t -> if x==0 then 0 else min x (minList t)

However, am I correct in believing that this sort of trick would not work in a strict evaluation language like OCaml, which would evaluate the whole of s before running minList? If so, what would be the correct way to optimize this in OCaml?

ADDITIONAL QUESTION: Ok, so if I understand that if statements are always lazy. But what about the following, for example: I have a function on int lists again which first checks whether or not the ith element is zero i.e.

f s = if s(i)==0 then 0 else g s

Here the input sequence s is present in both clauses of the if statement, but clearly for an efficient computation you would only want to evaluate s(i) in the first case. Here, would OCaml always evaluate all of s, even if the first case succeeds?

Upvotes: 0

Views: 255

Answers (4)

Jackson Tale
Jackson Tale

Reputation: 25812

In almost every modern programming language:

for expr1 && expr2, if expr1 is already false, then expr2 won't be evaluated.

for expr1 || expr2, if expr1 is already true, then expr2 won't be evaluated.

OCaml does this too.

Upvotes: 0

Aadit M Shah
Aadit M Shah

Reputation: 74204

First of all the minimum of an empty list is undefined, not 0. This makes sense, otherwise minList [1,2,3] would be 0 which is clearly not true. This is what ghci has to say:

Prelude> minimum []
*** Exception: Prelude.minimum: empty list

Hence your function should be written as:

let minList (x::t) = min x (minList t)

There are some problems with this definition though:

  1. It will still give an error because there's no pattern match for the empty list.
  2. It is not tail recursive.
  3. It doesn't stop if the head is 0.

So here's a better solution:

let minimum x xs = match x,xs
  | 0,xs        -> 0
  | x,[]        -> x
  | x,(y :: ys) -> minimum (min x y) ys

let minList = function
  | [] -> raise Failure "No minimum of empty list"
  | x::t -> minimum x t

The advantage of writing it like this is that minimum is tail recursive. Hence it will not increase the stack size. In addition if the head is 0 it will immediately return 0.

Lazy evaluation has no play here.

Upvotes: 1

John Smith Optional
John Smith Optional

Reputation: 24846

if expressions in ocaml don't follow the strict evaluation rule. Like || and &&, it's lazily evaluated. See this link: if expressions

Upvotes: 2

chi
chi

Reputation: 116139

In a strictly evaluated language, the whole list s would be evaluated. Still, 

minList s = 
    | [] -> 0
    | x :: t -> if x==0 then 0 else min x (minList t)

would not scan the whole list if a 0 is found.

The if construct has a "non-strict" semantics, in that it will evaluate only one branch, and not both. This holds in both strict and non strict languages.

An actual difference would be when calling a "user defined if" such as (using Haskell syntax):

myIf :: Bool -> a -> a
myIf b x y = if b then x else y

In a non strict language, calling myIf True 3 (nonTerminatingFunction ()) would yield 3, while in a strict language the same expression would loop forever.

Upvotes: 1

Related Questions