built-in lists vs inductively defined list

[José Miguel Vilaça]

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

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Stefan O'Rear]

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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Nils Anders Danielsson]

On Wed, 09 May 2007, Stefan O'Rear <[hidden email]> 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

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Tomasz Zielonka]

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

> On Wed, 09 May 2007, Stefan O'Rear <[hidden email]> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[jasonm]

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 <[hidden email]> wrote:

> On Wed, May 09, 2007 at 04:11:40PM +0200, Nils Anders Danielsson wrote:
> > On Wed, 09 May 2007, Stefan O'Rear <[hidden email]> 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
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[José Miguel Vilaça]

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: [hidden email]
[mailto:[hidden email]] 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 <[hidden email]> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Duncan Coutts]

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_deforestation

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


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Bas van Dijk-2]

On 5/9/07, Jason Morton <[hidden email]> 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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Bas van Dijk-2]

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 <[hidden email]> wrote:

> On 5/9/07, Jason Morton <[hidden email]> 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
>

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe