Haskell Strict Application

Haskell use Lazy evaluation by default, but also provides a strict version of function application with $!.

This means that f $! x behaves as normal function application f x except that the top level evaluation of the argument x is forced before the function f is applied.

Formally f $! x is only a redex once evaluation of x, using lazy evaluation as normal, has reached a point where it is known that the result is not undefined. Hereafter the expression can be reduced to the normal application f x.

Strict application are often used to improve space performance, since one can force argument-lists to be evaluated quickly instead of being repeatedly stored.

Curried Functions

When used with curried function with multiples arguments, e.g. f x y there are the three possibilities

• (f $! x) y forces top-level evaluation of x
• (f x) $! y forces top-level evaluation of y
• (f $! x) $! y forces top-level evaluation of x and y

Examples

Square function

With the function

square :: Int -> Int
square n = n * n

Strict application will evaluate like

  square $! (1+2)
= {applying +}
  square $! 3
 
= {applying $!}
  square 3
 
= {applying square}
   3 * 3
 
= {applying *}
   9

Saving Space with Strict Application

Consider a function sumwith that calculates the sum of a list of integers using an accumulator value:

sumwith :: Int -> [Int] -> Int
sumwith v [] = v
sumwith v (x:xs) = sumwith (v+x) xs

Then with lazy evaluation we have

sumwith 0 [1,2,3]
=     { applying sumwith }
sumwith (0+1) [2,3]
=     { applying sumwith }
sumwith ((0+1)+2) [3]
=     { applying sumwith }
sumwith (((0+1)+2)+3) []
=     { applying sumwith }
((0+1)+2)+3
=     { applying the first + }
(1+2)+3
=     { applying the first + }
3+3
=     { applying + }
6

where the entire summation ((0+1)+2)+3 is constructed before any of the additions are actually performed. In general the function will construct a summation whose size is proportional to the number of integers in the original list, which might require a lot of space.

One can instead use strict application to perform each addition as soon as it is introduced to improve space performance. We can force the evaluation of the accumulator value with

sumwith v [] = v
sumwith v (x:xs) = (sumwith $! (v+x)) xs

which could also be defined with sumwith = foldl' (+), with the Data.Foldable function foldl' that forces evaluation of its accumulator prior to processing tail of the list.

Now the evaluation will be

sumwith 0 [1,2,3]
=     { applying sumwith }
(sumwith $! (0+1)) [2,3]
=     { applying + }
(sumwith $! 1) [2,3]
=     { applying $! }
sumwith 1 [2,3]
=     { applying sumwith }
(sumwith $! (1+2)) [3]
=     { applying + }
(sumwith $! 3) [3]
=     { applying $! }
sumwith 3 [3]
=     { applying sumwith }
(sumwith $! (3+3)) []
=     { applying + }
(sumwith $! 6) []
=     { applying $! }
sumwith 6 []
=     { applying sumwith }
6

Resources

Hutton - Programming in Haskell pp. 223-225