Re: [Haskell-cafe] and from standard Prelude
On Wed, Aug 18, 2010 at 9:56 PM, wren ng thornton w...@freegeek.org wrote:
Oleg Lobachev wrote:
#ifdef USE_REPORT_PRELUDE
and = foldr () True
or = foldr (||) False
#else
and [] = True
and (x:xs) = x and xs
or [] = False
or (x:xs) = x || or xs
{-# RULES
and/build forall (g::forall b.(Bool-b-b)-b-b) .
and (build g) = g () True
or/build forall (g::forall b.(Bool-b-b)-b-b) .
or (build g) = g (||) False
#-}
#endif
The thing I find puzzling is that the foldr is inlined. The (regular) clever
optimizations for build/foldr seem like they should already handle this
without the need for the extra rules. I wonder how much is gained by
specializing to ()/True instead of relying on the regular deforestation?
The above code does not inline and / or, *unless they are fused using
the RULES.* There's not really any benefit to inlining them
otherwise, and it duplicates code.
-Jan-Willem Maessen
--
Live well,
~wren
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] and from standard Prelude
On 8/24/10 1:55 PM, Jan-Willem Maessen wrote: On Wed, Aug 18, 2010 at 9:56 PM, wren ng thorntonw...@freegeek.org wrote: The thing I find puzzling is that the foldr is inlined. The (regular) clever optimizations for build/foldr seem like they should already handle this without the need for the extra rules. I wonder how much is gained by specializing to ()/True instead of relying on the regular deforestation? The above code does not inline and / or, *unless they are fused using the RULES.* There's not really any benefit to inlining them otherwise, and it duplicates code. Ah, that makes sense. Thanks. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] and from standard Prelude
Hello all,
the and function, and :: [Bool] - Bool is defined in two different ways in the
latest Prelude.
I would expect it to be
and = foldr () True
However, there is a further recursive definition, and it is the one used! See
http://haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/src/GHC-List.html#and
#ifdef USE_REPORT_PRELUDE
and = foldr () True
or = foldr (||) False
#else
and [] = True
and (x:xs) = x and xs
or [] = False
or (x:xs) = x || or xs
{-# RULES
and/build forall (g::forall b.(Bool-b-b)-b-b) .
and (build g) = g () True
or/build forall (g::forall b.(Bool-b-b)-b-b) .
or (build g) = g (||) False
#-}
#endif
Is there any reason for that besides some clever optimizations? I am
particularly interested in the behavior of and for infinite lists and these two
versions are equivalent in this aspect.
Greetings,
Oleg
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] and from standard Prelude
Oleg Lobachev lobac...@mathematik.uni-marburg.de writes:
#else
and [] = True
and (x:xs) = x and xs
or [] = False
or (x:xs) = x || or xs
{-# RULES
and/build forall (g::forall b.(Bool-b-b)-b-b) .
and (build g) = g () True
or/build forall (g::forall b.(Bool-b-b)-b-b) .
or (build g) = g (||) False
#-}
#endif
Is there any reason for that besides some clever optimizations? I am
particularly interested in the behavior of and for infinite lists and
these two versions are equivalent in this aspect.
Precisely for clever optimisations. See the paper A Short Cut to
Deforestation by Andrew Gill, John Launchbury and Simon Peyton Jones
(from 1993 apparently; I'm going off a copy I have locally).
--
Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com
IvanMiljenovic.wordpress.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] and from standard Prelude
On 18 August 2010 10:05, Oleg Lobachev lobac...@mathematik.uni-marburg.de wrote: Hello all, the and function, and :: [Bool] - Bool is defined in two different ways in the latest Prelude. I would expect it to be and = foldr () True However, there is a further recursive definition, and it is the one used! This is just an issue of specification vs implementation. The spec from the H98 report is and = foldr () True An H98 implementation must provide an implementation of 'and' that is equal to this specification. So the above can be used as the implementation, or a directly recursive implementation or versions using build/fold or unfold/destroy fusion, or any other implementation would also be ok so long as they are equal to the spec. As Ivan says, GHC's implementation of 'and' uses build/fold fusion. Note that 'equal' includes all partial and total lists, so you can rely on the above spec to reason about the behaviour on infinite lists and expect that reasoning to work for correct H98 implementations. That said, there are a couple functions where the obviously sensible, and standard implementations differ from the H98 spec for some partial values. Notably splitAt is specified badly in the H98 report (it is too lazy). Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] and from standard Prelude
Hello, On Aug 18, 2010, at 13:44 , Duncan Coutts wrote: This is just an issue of specification vs implementation. The spec from the H98 report is and = foldr () True [snip] Note that 'equal' includes all partial and total lists, so you can rely on the above spec to reason about the behaviour on infinite lists and expect that reasoning to work for correct H98 implementations. ok, thank you. It was precisely the reason for my question. I used the fold-based definition in my ramblings and then bothered to look into the Prelude code. ;) That said, there are a couple functions where the obviously sensible, and standard implementations differ from the H98 spec for some partial values. Notably splitAt is specified badly in the H98 report (it is too lazy). By the way, does some good reading on streams in Haskell exist? I am interested primarily in a theoretical foundation, which should however be somehow related to Haskell. My guess would be the relation of streams, represented as lazy, not completely evaluated lists, and the evaluation strategies. The practical part is easier, feeding [1..] to various functions in GHCi. I have found [Ennals2003optimistic], but it seems to go in wrong direction. [Ennals2003optimistic]: Robert Ennals, Simon Peyton Jones. Optimistic evaluation: an adaptive evaluation strategy for non-strict programs. ICFP 2003. http://portal.acm.org/citation.cfm?id=944705.944731 Greetings, Oleg ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] and from standard Prelude
On 18 August 2010 13:29, Oleg Lobachev lobac...@mathematik.uni-marburg.de wrote: By the way, does some good reading on streams in Haskell exist? I am interested primarily in a theoretical foundation, which should however be somehow related to Haskell. My guess would be the relation of streams, represented as lazy, not completely evaluated lists, and the evaluation strategies. The practical part is easier, feeding [1..] to various functions in GHCi. I have found [Ennals2003optimistic], but it seems to go in wrong direction. If you mean streams as in stream fusion then I hope chapter 3 of my PhD thesis will be of some help (when it is finally published). If you mean streams as in always-infinite co-inductive sequences then a good starting point is probably Functional Pearl: Streams and Unique Fixed Points by Ralf Hinze. Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] and from standard Prelude
Oleg Lobachev wrote:
#ifdef USE_REPORT_PRELUDE
and = foldr () True
or = foldr (||) False
#else
and [] = True
and (x:xs) = x and xs
or [] = False
or (x:xs) = x || or xs
{-# RULES
and/build forall (g::forall b.(Bool-b-b)-b-b) .
and (build g) = g () True
or/build forall (g::forall b.(Bool-b-b)-b-b) .
or (build g) = g (||) False
#-}
#endif
Is there any reason for that besides some clever optimizations?
The thing I find puzzling is that the foldr is inlined. The (regular)
clever optimizations for build/foldr seem like they should already
handle this without the need for the extra rules. I wonder how much is
gained by specializing to ()/True instead of relying on the regular
deforestation?
--
Live well,
~wren
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
