CODEWITHSUNDEEP
haskellrecursionpattern-matchinglazy-evaluationfold
Calvin S
Calvin S

Reputation: 33

Strictness of pattern matching vs. deconstructing

I'm trying to define primitive recursion in term of foldr, as explained in A tutorial on the universality and expressiveness on fold chapter 4.1.

Here is first attempt at it

simpleRecursive f v xs = fst $ foldr g (v,[]) xs
  where 
    g x (acc, xs) = (f x xs acc,x:xs)

However, above definition does not halt for head $ simpleRecursive (\x xs acc -> x:xs) [] [1..]

Below is definition that halt

simpleRecursive f v xs = fst $ foldr g (v,[]) xs
  where 
    g x r = let (acc,xs) = r
            in (f x xs acc,x:xs)

Given almost similar definition but different result, why does it differ? Does it have to do with how Haskell pattern match?

Upvotes: 3

Views: 200

Answers (1)

Cactus
Cactus

Reputation: 27626

The crucial difference between the two functions is that in

g x r = let (acc, xs) = r
        in (f x xs acc, x:xs)

The pattern match on the tuple constructor is irrefutable, whereas in 

g x (acc, xs) = (f x xs acc, x:xs)

it is not. In other words, the first definition of g is equivalent to

g x ~(acc, xs) = (f x xs acc, x:xs)

Upvotes: 3

Related Questions