let cons used both concretely and abstractly

Question

I was doing this

reverseP x = pour x []
  where pour []    ans = ans
        pour (h:t) ans = pour t (h:ans)

where a parameter accumulator is better than the crude and costly version

reverse [] = []
reverse (h:t) = reverse t ++ [h]

But then I wanted to see if I could redo reverseP with let just as an exercise. I finally got this to work

reverseP2 x =
  let
    (t:ts) = x
    pour [] ans = ans
    pour (t:ts) ans = pour ts (t:ans)
  in pour x []

but I don't know why it's working. It's not realistic to expect to go on with Haskell writing working code that I don't understand, so I thought I'd better find out why this works. What's confusing me is that I've assigned the incoming x to the cons (Is this considered a tuple?) (t:ts), but then I use (t:ts) in an "abstract" way as an argument to pour two lines later. Since it works, the recursions must indeed be breaking down the list correctly, i.e., the cons (t:ts) defined in the first line is being properly taken apart. Also confusing is how the let form above allows pour to be defined twice in the pattern matching way. I tried it with guards to keep it to only one pour, but then the (t:ts) did not properly break down -- part of why I'm surprised this works. So how can the same cons (t:ts) be both concrete and abstract, and how can pour recurse and behave pattern matching-wise inside the let? Also, could reverseP2 be considered tail-recursive?

Answer 1

Let’s try compiling this with warnings turned on:

Prelude> :set -Wall
Prelude> :{
Prelude| reverseP2 x =
Prelude|   let
Prelude|     (t:ts) = x
Prelude|     pour [] ans = ans
Prelude|     pour (t:ts) ans = pour ts (t:ans)
Prelude|   in pour x []
Prelude| :}

<interactive>:7:11: warning: [-Wname-shadowing]
    This binding for `t' shadows the existing binding
      bound at <interactive>:5:6

<interactive>:7:13: warning: [-Wname-shadowing]
    This binding for `ts' shadows the existing binding
      bound at <interactive>:5:8

What is this message saying? It says that the second definitions of t and ts are shadowing the first ones. That is, the two ts and the two tss do not refer to the same value — the first t:ts is x, while the second t:ts refers to a parameter of pour. This is confusing! So let’s rename one of them:

reverseP2 x =
  let
    (t:ts) = x
    pour [] ans = ans
    pour (a:as) ans = pour as (a:ans)
  in pour x []

And in fact, this shows that you don’t even need t and ts, so let’s get rid of them:

reverseP2 x =
  let
    pour [] ans = ans
    pour (a:as) ans = pour as (a:ans)
  in pour x []

Finally, while I’m at it, I should note that for longer definitions such as that of pour, it is considered idiomatic to use a where block rather than let:

reverseP2 x = pour x []
  where
    pour [] ans = ans
    pour (a:as) ans = pour as (a:ans)

I've assigned the incoming x to the cons (Is this considered a tuple?) (t:ts) …

No, this is not at all a tuple; this is a list. If it were a tuple, it would need to have type (a, (a, (a,a))) or similar; but as a list, it has type [a].

Also confusing is how the let form above allows pour to be defined twice in the pattern matching way.

But it’s not defining it twice! You have only one definition of pour, which depends on the input as follows: if the input is an empty list, pour returns ans, else it returns pour as (a:ans).

Also, could reverseP2 be considered tail-recursive?

I believe so but generally speaking tail-recursion is considered unimportant in Haskell (see e.g. discussion starting here).

EDIT: As @DanienWagner points out in the comments, reverseP2 is not recursive at all! It is pour which is tail-recursive.