built-in lists vs inductively defined list - Haskell-Cafe - Haskell.org

newer
Re: [Haskell-cafe] Debugging

built-in lists vs inductively defined list

older
Vanishing polymorphism

José Miguel Vilaça

9 May 2007 9 May '07

1:45 p.m.

Hi, Can someone tell me if would be any difference (beside syntax) between the built-in Haskell list with [] and : and lists given by a inductive datatype definition like data List a = Nil | Cons a (List a) This is, is any of the compilers doing some special optimizations for the built-in lists? Best Miguel Vilaça

Attachments:

attachment.html (text/html — 2.9 KB)

Reply

Sign in to reply online Use email software

Show replies by date

Stefan O'Rear

9 May 9 May

1:52 p.m.

On Wed, May 09, 2007 at 02:45:34PM +0100, Jos? Miguel Vila?a wrote:

Can someone tell me if would be any difference (beside syntax) between the built-in Haskell list with [] and : and lists given by a inductive datatype definition like

data List a = Nil | Cons a (List a)

This is, is any of the compilers doing some special optimizations for the built-in lists?

To the best of my knowledge, there are no optimizations specific to [] in the compiler proper. However, the standard library has a *lot* of speed hacks you will need to duplicate! Stefan

Reply

Sign in to reply online Use email software

Nils Anders Danielsson

2:11 p.m.

On Wed, 09 May 2007, Stefan O'Rear wrote:

To the best of my knowledge, there are no optimizations specific to [] in the compiler proper.

However, the standard library has a *lot* of speed hacks you will need to duplicate!

Some of which are not expressible in "ordinary" Haskell (rewrite rules used for short-cut deforestation). -- /NAD

Reply

Sign in to reply online Use email software

Tomasz Zielonka

3:12 p.m.

On Wed, May 09, 2007 at 04:11:40PM +0200, Nils Anders Danielsson wrote:

On Wed, 09 May 2007, Stefan O'Rear wrote:

...
To the best of my knowledge, there are no optimizations specific to [] in the compiler proper.

However, the standard library has a *lot* of speed hacks you will need to duplicate!

Some of which are not expressible in "ordinary" Haskell (rewrite rules used for short-cut deforestation).

I just want to note that no particular compiler was named so far in this thread and this is a very compiler specific area. To OP: are you asking about the language or some particular implementation? Best regards Tomasz

Reply

Sign in to reply online Use email software

Jason Morton

4:08 p.m.

I'd love to understand these rewrite-rules a little better; could anyone point me to where (if?) they are documented? On 5/9/07, Tomasz Zielonka wrote:

On Wed, May 09, 2007 at 04:11:40PM +0200, Nils Anders Danielsson wrote:

...
On Wed, 09 May 2007, Stefan O'Rear wrote:

...
To the best of my knowledge, there are no optimizations specific to [] in the compiler proper.

However, the standard library has a *lot* of speed hacks you will need to duplicate!

Some of which are not expressible in "ordinary" Haskell (rewrite rules used for short-cut deforestation).

I just want to note that no particular compiler was named so far in this thread and this is a very compiler specific area.

To OP: are you asking about the language or some particular implementation?

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

Reply

Sign in to reply online Use email software

Duncan Coutts

7:18 p.m.

On Wed, 2007-05-09 at 09:08 -0700, Jason Morton wrote:

I'd love to understand these rewrite-rules a little better; could anyone point me to where (if?) they are documented?

Here's a list of papers on fusion and deforestation: http://haskell.org/haskellwiki/Research_papers/Compilation#Fusion_and_defore... Specifically you want to read about short-cut fusion and rules. I'd recommend: A short cut to deforestation Shortcut fusion for accumulating parameters and zip-like functions Playing by the rules: rewriting as a practical optimisation technique in GHC Duncan

Reply

Sign in to reply online Use email software

Bas van Dijk

10 May 10 May

8:08 a.m.

On 5/9/07, Jason Morton wrote:

I'd love to understand these rewrite-rules a little better; could anyone point me to where (if?) they are documented?

They are documented in the GHC User Guide: http://www.haskell.org/ghc/docs/latest/html/users_guide/rewrite-rules.html regards, Bas van Dijk

Reply

Sign in to reply online Use email software

Bas van Dijk

8:39 a.m.

There's also documentation about rewrite rules on the Haskell en GHC wikis: http://haskell.org/haskellwiki/Playing_by_the_rules http://hackage.haskell.org/trac/ghc/wiki/RewriteRules Bas On 5/10/07, Bas van Dijk wrote:

On 5/9/07, Jason Morton wrote:

...
I'd love to understand these rewrite-rules a little better; could anyone point me to where (if?) they are documented?

They are documented in the GHC User Guide:

http://www.haskell.org/ghc/docs/latest/html/users_guide/rewrite-rules.html

regards,

Bas van Dijk

Reply

Sign in to reply online Use email software

José Miguel Vilaça

9 May 9 May

5:15 p.m.

Hi again, IMHO for what concerns to the language they only differ in syntax. They are equal up to constructor names. What could be the case is that some compiler could do some optimizations that end up with better performance in time and space when using lists. But for what people gently ask me, the optimizations are in the functions over list and not in the data structure itself. Do you know something about an implementation that does something about the data structure itself? Best Miguel Vilaça -----Mensagem original----- De: haskell-cafe-bounces@haskell.org [mailto:haskell-cafe-bounces@haskell.org] Em nome de Tomasz Zielonka Enviada: quarta-feira, 9 de Maio de 2007 16:13 Para: Haskell Cafe Assunto: Re: [Haskell-cafe] built-in lists vs inductively defined list On Wed, May 09, 2007 at 04:11:40PM +0200, Nils Anders Danielsson wrote:

On Wed, 09 May 2007, Stefan O'Rear wrote:

...
To the best of my knowledge, there are no optimizations specific to [] in the compiler proper.

However, the standard library has a *lot* of speed hacks you will need to duplicate!

Some of which are not expressible in "ordinary" Haskell (rewrite rules used for short-cut deforestation).

I just want to note that no particular compiler was named so far in this thread and this is a very compiler specific area. To OP: are you asking about the language or some particular implementation? Best regards Tomasz _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply

Sign in to reply online Use email software

6634

Age (days ago)

6635

Last active (days ago)

Download

8 comments

7 participants

tags

participants (7)

Bas van Dijk
Duncan Coutts
Jason Morton
José Miguel Vilaça
Nils Anders Danielsson
Stefan O'Rear
Tomasz Zielonka