CODEWITHSUNDEEP
listfunctionhaskellfunctional-programming
sgman
sgman

Reputation: 89

Lists in functional programming, more specifically in Haskell

I am studying Haskell and saw this question :

h [] = []
h [x] = []
h (x:y:ys) = (x <= y): (h (y:ys))

the questions are, (1) what is the output type of h? (2) if length of xs is 100 then what is length of h xs? (3) calculate h [1..5] and (4) h [1,2,1,2,1]

I don't understand how to proceed with this. What does the third condition h (x:y:ys) = (x <= y): (h (y:ys)) mean ?

Upvotes: 1

Views: 153

Answers (2)

chepner
chepner

Reputation: 531165

The full type of h is Ord a => [a] -> [Bool].

  1. The first two equations imply that both the input and output are lists of some type. For our first pass, we'll assume h :: [a] -> [b]; we'll figure out what constraints, if any, belong on a and b next.

  2. The first two values in the input list in the 3rd equation are used by (<=) :: Ord a => a -> a -> Bool, so we now know that the input list must be Ord a => [a].

  3. Further, the result of (<=) is prepended to the return value of the recursive call to h. For that to work, since (:) :: a -> [a] -> [a], we know that h must return a value of type [Bool].

Upvotes: 4

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476604

what does the third condition h (x:y:ys) = (x <= y): (h (y:ys)) really mean ?

Well it is short for:

h (x:(y:ys)) = (x <= y): (h (y:ys))

Well it matches given the list contains at least two elements. In that case it compares the first with the second element x <= y and if the outcome, a Bool is placed in the head of the resulting list. It next does a recursive call to h with the second element and the remaining elements.

So what does the function calculates? (1) For a given list of n elements, it returns a list of n-1 booleans that says for every two consecutive numbers whether the list is (not strictly) increasing. So to answer you first question.

Furthermore for a given list of n elements, it returns a list of n-1 elements, so if you give it a list of 100 elements, it (2) returns a list of 99 elements.

Finally for h [1..5] it means we will get (3) [True,True,True,True] and for h [1,2,1,2,1] we will get (4) [True,False,True,False].

Upvotes: 4

Related Questions