CODEWITHSUNDEEP
haskellsyntactic-sugar
Marcin
Marcin

Reputation: 430

Haskell stripping function of syntactic sugar

I'm wondering how would the following function look without any syntactic sugar: 

tails1 :: [a] -> [[a]]
tails1 [] = [[]]
tails1 xs@(x:xs') = xs:tails1 xs'

I'm mostly concerned with the usage of the @ operator, I've tried what follows, but that's obviously not the correct way

tails1 ((:) x ((:) xs' [])) = xs:tails1 xs'

Upvotes: 0

Views: 187

Answers (3)

Daniel Wagner
Daniel Wagner

Reputation: 153212

In other answers, we have seen two proposals:

tailsA (x:xs') = (x:xs'):tailsA xs
tailsB xs = xs:tailsB (tail xs)

The former has the right denotational semantics, but the wrong operational semantics. The original tails has only one call to (:); one might therefore worry that a sufficiently stupid compiler would allocate extra cons cells when running tailsA compared to the original definition of tails. The latter also has the right denotation, and only has one call to (:), but inserts a brand new function tail which does not appear in the original; this transformation seems to require some programmer insight to perform. Below, I will show how the original definition may be transformed into one with no at-patterns in a way that does not require programmer insight (hence can be performed by a compiler) and which does not risk additional allocation.

tailsC xs = case xs of
    x:xs' -> xs:tailsC xs'

Of special interest here: the original equation's right-hand side appears verbatim as the right-hand side of the case statement. (Neither of tailsA or tailsB contains the original equation's right-hand side as a subterm at all.) The general translation of at patterns suggested by this special-case transformation is not fully correct (since xs matches any value whereas xs@(x:xs') matches only non-empty lists); a full treatment of turning Haskell-style patterns into GHC-Core-style case statements (which scrutinize only a single variable, and whose patterns all contain exactly one constructor) is out of scope for a StackOverflow answer. There have been several research papers discussing how to do this correctly, efficiently, and producing speedy code; see also the related question Algorithm for type checking ML-like pattern matching? and basically all of the results in the Google Scholar search for compiling pattern matching.

But the basic idea is that name@pattern matches exactly when pattern matches (binding all the same names pattern does to all the same values), but additionally binds name to the full value.

Upvotes: 5

Gabriel Ciubotaru
Gabriel Ciubotaru

Reputation: 1092

First you need to understand the list data type. Here are the list data constructors:

[] :: [a]
(:) :: a -> [a] -> [a]

where:

  1. [] create an empty list
  2. (:) takes an a , a list of a and returns a list of a with the new element appedned

Let say you have a list [1,2,3,4]. This can be written as (:) 1 ((:) 2 ((:) 3 ((:) 4 []))) In expression x:xs', x hold 1 and xs' will hold (:) 2 ((:) 3 ((:) 4 [])). In other words : takes an element and a list, appending this element to the list.

The equivalent expression for your example is:

tails1 ((:) x xs') = ((:)x xs'):tails1 xs'

Where x is holding the first element of the list and xs' the rest of the list. xs' cannot hold multiple elements. In your example tails1 ((:) x ((:) xs' [])) = xs:tails1 xs', xs' should hold everything except first element and []. (in my examle it should be 2:3:4 which is not a valid list because is not ended by []).

Upvotes: 4

jwodder
jwodder

Reputation: 57630

Because the tails1 [] entry comes first, we don't need to ensure that the desugared tails1 xs@(x:xs') only matches nonempty lists, as they are guaranteed to be nonempty. Thus, the only effect of writing xs@(x:xs') is to give us access to both xs and tail xs, and so the line can be rewritten as:

tails1 xs = xs : tails1 (tail xs)

Upvotes: 2

Related Questions