Search code examples
haskellfunctional-programmingdeclarative

length vs head vs last in Haskell


I know 2 of these statements are true, but I dont know which

Let e be an expression of type [Int]

  1. there exists e such that: Evaluation of head e won't finish but last e will

  2. there exists e such that: Evaluation of last e won't finish but head e will

  3. there exists e such that: Evaluation of length e won't finish but last e will

Seems clear to me that 2 is true, but I can't see how 1 or 3 can be true.

My thinking is that in order to calculate the length of a list you need to get to the last one, making 1 and 3 impossible


Solution

  • Since this is a test question, I won't answer it directly, but instead, here are some hints; it'd be better if you work this out yourself.

    Since we're talking about computations that don't terminate, it might be useful to define one such computation. However, if this confuses you you can safely ignore this and refer only to examples that don't include this.

    -- `never` never terminates when evaluated, and can be any type.
    never :: a
    never = never
    

    Question 1

    Consider the list [never, 1], or alternatively the list [last [1..], 1] as suggested by @chi.


    Question 2

    Consider the list [1..], or alternatively the list [1, never].


    Question 3

    Consider the definition of length:

    length [] = 0
    length (_:xs) = 1 + length xs
    

    Under what conditions does length not terminate? How does this relate to last?