Thanks. Pattern matching and memory management in Haskell (or may be GHC implementation of it) is somewhat of a mystery to me. Are there any references that explains the underlying implementation? Daryoush On Mon, Sep 8, 2008 at 6:37 PM, Mauricio wrote:

abs (Pt {pointx = x, pointy = y}) = sqrt (x*x + y+y)

...

Why is it pointx=x and not x=pointx?

Your intuition is probably telling you that this is something like:

abs (point) = sqrt (x*x+y*y) where {x=pointx point ; y=pointy point}

Actually, it's an example of pattern matching:

abs (Pt {pointx=3 , pointy=4}) = 5 abs (Pt {pointx=3 , pointy=y}) = sqrt (9+y*y) abs (Pt {pointx=z , pointy=z}) = (sqrt 2)*z

etc.

Best, Maurício

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Daryoush Weblog: http://perlustration.blogspot.com/

Justin Bailey wrote:

2008/9/8 Daryoush Mehrtash

...

Thanks.

Pattern matching and memory management in Haskell (or may be GHC implementation of it) is somewhat of a mystery to me. Are there any references that explains the underlying implementation?

Be careful what you ask for. This paper is 16 years old but fairly relevant. Click the "view or download" link at the bottom:

"Implementing Lazy Functional Languages on Stock Hardware: The Spineless Tagless G-Machine" http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.3729

That's an excellent paper for getting down to the gritty details of what's going on under the covers. However, I think it's not clear that that's what you're really looking for; you needn't know anything about the STG in order to know how pattern matching works enough to use it. In short, a pattern is a (free) variable, or a data constructor applied to patterns. So if we have:

data MyList = Nil | Cons Int MyList

Then we can have the patterns: Nil, (Cons x xs), (Cons 0 xs),..., (Cons x Nil), (Cons 0 Nil),..., (Cons x (Cons x2 xs)), etc. Other notes: * As demonstrated above, numeric literals count as "data constructors". * Since a data constructor can be an infix operator (either spelled with backticks or a symbolic name beginning with ':' ) we can also write our patterns with infix notation. * Even though there is an intentional homoiconicity between patterns and an expression of data constructors, you can't use arbitrary expressions. This falls out from only allowing data constructors in patterns, rather than any arbitrary function. ** In particular, you can't use partial application. You also can't use anything like (.), ($), flip,... ** (While n+k patterns exist for legacy reasons, they are an abomination. They should not be used and are slated for removal in haskell prime.) ** For record syntax this homoiconicity means that you get Foo{xpart=x} as a pattern binding the variable x. This follows because that's what the expression would look like to construct a Foo setting the xpart to a variable x. Perhaps confusingly, the '=' involved here is the one from record syntax, not the one from let bindings. The homoiconicity generally makes code easier to read, though it can be somewhat confusing when discussing theoretical concerns. The reason is that a single lexeme, e.g. 'Cons', is being used both as a data constructor (in expressions) and as a data *de*structor (in patterns). Identically, a field name in a record is used both as an injector and as a projector. This conceptual overloading is perfectly valid, but it sometimes leads to people conflating the ideas which is invalid. There are sometimes reasons to want to throw a wrench into the works, breaking up the homoiconicity. One particular example (which I believe will be available in 6.10 though it's not approved for haskell prime) is to allow "view patterns". The idea behind view patterns is to allow functions to be called behind the scenes in order to convert the in-memory representation into a view type, and then do pattern matching on that view of the value rather than on the value itself. There are two primary uses of this: (1) improving legibility of pattern matching for complex datastructures, (2) allowing multiple types to all be pattern matched interchangeably, e.g. association lists, Maps, HashMaps,... There are drawbacks to views (and anything else that breaks homoiconicity). First off is that it greatly complicates the story of what's going on during pattern matching. More importantly, however, is that it means that pattern matches are no longer in correspondence with the in-memory representations of values. This means that there is a hidden performance cost which can get quite high for deep patterns. -- Live well, ~wren

Hello Mauricio, Wednesday, September 10, 2008, 4:07:41 PM, you wrote:

Do you have any reference for that use of infixing constructors by start their name with ':'? That's interesting, and I didn't know about it.

really? ;) sum (x:xs) = x + sum xs sum [] = 0 -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

On Wed, 2008-09-10 at 11:54 -0400, Brandon S. Allbery KF8NH wrote:

On 2008 Sep 10, at 8:53, Bulat Ziganshin wrote:

...

Wednesday, September 10, 2008, 4:07:41 PM, you wrote:

...

Do you have any reference for that use of infixing constructors by start their name with ':'? That's interesting, and I didn't know about it.

really? ;)

sum (x:xs) = x + sum xs sum [] = 0

I think that only counts as the origin of the idea; isn't :-prefixed infix constructors a ghc-ism?

http://www.haskell.org/ghc/docs/latest/html/users_guide/data-type-extensions...

That link is for type constructors, not data constructors; for data constructors, go to http://haskell.org/onlinereport/lexemes.html and search for `Operator symbols'. (The Haskell 98 Report seems to not have internal anchor tags for hot-linking, unfortunately). jcc

On Wed, 2008-09-10 at 21:32 -0300, Mauricio wrote:

...

...

...

...

Do you have any reference for that use of infixing constructors by start their name with ':'? (...)

...

(...) for data constructors, go to

http://haskell.org/onlinereport/lexemes.html

and search for `Operator symbols'. (...)

Here it is:

“Operator symbols are formed from one or more symbol characters, as defined above, and are lexically distinguished into two namespaces (Section 1.4):

* An operator symbol starting with a colon is a constructor.(...)”

Cool! What is the syntax for using that in 'data'? Is it something like “data X = Y | Int :°& Double”?

Right. So then (:°&) :: Int -> Double -> X jcc