haskellpattern-matchinglazy-evaluationstrictness

Irrefutable/lazy pattern exercise in Haskell wikibook


Half way down here...

https://en.wikibooks.org/wiki/Haskell/Laziness

...is an exercise asking about the effects of changes to an alternative implementation of the head function that uses irrefutable patterns. It provides a definition of head' as follows, noting that it will always return undefined due to irrefutable matching of the first equation:

head' :: [a] -> a
head' ~[]     = undefined
head' ~(x:xs) = x

Then it asks:

In GHC 7.8.4 it seems that changing the order "helps" at least to the extent of making this function behave like the regular partial version of head, albeit with a different exception in the empty list case. The answer to the second question would appear to me to be "no", but given the "if so, how" addendum, it feels like I must be missing something here too. Can anyone enlighten me? The solutions link on the page does not cover this exercise unfortunately.


Solution

  • I'm not sure what the wikibook means by "help". You are correct that changing the order will make it behave essentially like the normal head. Similarly, you are correct that making the first pattern refutable would also make it behave like head. I'm going to say that these questions are confused; they are definitely confusing.

    We can verify these answers by calculation (including calculation with GHC):

    head [] = ⊥
    head (x:xs) = x
    head ⊥ = ⊥
    
    head' [] = ⊥
    head' (x:xs) = ⊥
    head' ⊥ = ⊥
    
    head1 [] = ⊥
    head1 (x:xs) = x
    head1 ⊥ = ⊥
    
    head2 [] = ⊥
    head2 (x:xs) = x
    head2 ⊥ = ⊥
    

    head is the standard library version. head' is the version from the wikibook. head1 is the version with the clauses swapped. head2 is the version with the first pattern being a refutable match against []. ⊥ is read as "bottom" and represents a non-terminating or exceptional computation, i.e. undefined.

    What I would've expected is examples like the following where there are subtle but significant differences between refutable and irrefutable patterns:

    konst ~() = ()
    
    konst' () = ()
    
    partialId ~(x:xs) = x:xs
    
    partialId' (x:xs) = x:xs