How to force evaluation in Haskell?

Question

I am relatively new to Haskell and I am trying to learn how different actions can be executed in sequence using the do notation. In particular, I am writing a program to benchmark an algorithm (a function)

foo :: [String] -> [String]

To this purpose I would like to write a function like

import System.CPUTime

benchmark :: [String] -> IO Integer
benchmark inputList = do
                         start <- getCPUTime
                         let r = foo inputList
                         end <- getCPUTime
                         return (end - start) -- Possible conversion needed.

The last line might need a conversion (e.g. to milliseconds) but this is not the topic of this question.

Is this the correct way to measure the time needed to compute function foo on some argument inputList?

In other words, will the expression foo inputList be completely reduced before the action end <- getCPUTime is executed? Or will r only be bound to the thunk foo inputList?

More in general, how can I ensure that an expression is completely evaluated before some action is executed?

This question was asked a few months ago on programmers (see here) and had an accepted answer there but it has been closed as off-topic because it belongs on stack overflow. The question could not be moved to stack overflow because it is older than 60 days. So, in agreement with the moderators, I am reposting the question here and posting the accepted question myself because I think it contains some useful information.

If you are just interested in benchmarking, you might want to check out the [criterion](http://hackage.haskell.org/package/criterion) library. — hugomg, Jan 04 '13 at 18:57
The `foo` function will not execute by the time you reach the final line. Haskell functions are only evaluated on demand, so you will need to do something with that `r` value before the assignment to `end`. — Michael Steele, Jan 04 '13 at 21:32

score 22 · Answer 1 · edited Apr 12 '17 at 07:31

22

Answer originally given by user ysdx on programmers:

Indeed you version will not benchmark your algorithm. As r is not used it will not be evaluated at all.

You should be able to do it with DeepSeq:
benchmark :: [String] -> IO Integer
benchmark inputList = do
                     start <- getCPUTime
                     let r = foo inputList
                     end <- r `deepseq` getCPUTime
                     return (end - start)
(a `deepseq` b) is some "magic" expression which forces the complete/recursive evaluation of a before returning b.

edited Apr 12 '17 at 07:31

Community

1
1

answered Jan 04 '13 at 18:53

Giorgio

5,023
6
41
71

2

Usual way to save yourself from taking credit for others' work is to make the answer community wiki. Then the answer can still be upvoted/accepted, but you won't get the credit :) – Ben Millwood Jan 04 '13 at 22:35
2

I did not know that, thanks. I have set the community wiki tag. Now the two upvoters can remove the upvote, if they happen to read this again. – Giorgio Jan 04 '13 at 22:38
I still dont get it. What if I write `let _ = a \`deepseq\` ()` instead? Will it force the evaluation? – Nawaz Jul 07 '20 at 01:10
@Nawaz no. It only means that if a `deepseq` b is evaluated, then a will be fully evaluated before b is returned. In your example, it does not appear that the expression a `deepseq` () is evaluated. – jforberg Feb 14 '21 at 14:21

J Fritsch · Answer 2 · 2013-01-04T19:59:47.763

14

I would use the language extension -XBangPatterns, I find that quite expressive in such situations. So you would have to say "let !r = foo inputList" as in:

{-# LANGUAGE BangPatterns #-}
import System.CPUTime

benchmark :: [String] -> IO Integer
benchmark inputList = do
                         start <- getCPUTime
                         let !r = foo inputList
                         end <- getCPUTime
                         return (end - start)

edited Jan 04 '13 at 19:59

answered Jan 04 '13 at 19:37

J Fritsch

3,338
1
18
40

3

That would only evaluate the result to the outermost constructor, here, complete evaluation is desired. – Daniel Fischer Jan 04 '13 at 20:01
2

Do bang patterns ensure complete evaluation or will the expression be reduced to weak head normal form (http://stackoverflow.com/questions/6872898/haskell-what-is-weak-head-normal-form)? – Giorgio Jan 04 '13 at 20:03
You can use BangPatterns in foo as well. – J Fritsch Jan 04 '13 at 20:17
2

@Giorgio WHNF, bang patterns are a nicer `seq`. – Daniel Fischer Jan 04 '13 at 20:27
@Daniel Fischer: So this would be sufficient if the evaluation of `foo` introduced some thunk that is in WHNF but does not represent the final result. – Giorgio Jan 04 '13 at 20:30
@Giorgio I don't understand what you mean. It will find out whether `foo inputList` is `[]` or `(_:_)`, nothing more unless that is required to find out whether the result is empty or not. – Daniel Fischer Jan 04 '13 at 20:33
@Daniel Fischer: When the second `getCPUTime` is called, I want that the result list has been completely constructed. I do not want to have a thunk like `"A" : ` which, as far as I understand, is in WHNF. When `getCPUTime` is called, the list should already have the content that would be printed by `putStrLn`. – Giorgio Jan 04 '13 at 20:36
1

@Giorgio Even that is more than WHNF, ` : ` is WHNF. You want complete evaluation, that is NF, so `deepseq` or ensuring that `foo`'s result is completely evaluated when it is forced to WHNF. The latter is usually painful. – Daniel Fischer Jan 04 '13 at 20:41
@Daniel Fischer: But I need normal form because I want to measure the performance of an algorithm. I guess normal form is the only possibility. I had a similar question (http://stackoverflow.com/questions/13963102/how-to-force-strict-evaluation-of-a-sequence-of-bytestring) regarding sequences using bytestring. As far as I understand, in general one always needs `deepseq` to measure performance. – Giorgio Jan 04 '13 at 20:47
let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/22203/discussion-between-daniel-fischer-and-giorgio) – Daniel Fischer Jan 04 '13 at 20:53

How to force evaluation in Haskell?

2 Answers2

Linked