Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Definition of last: why complicate it? (Rudy Matela)
2. Re: Definition of last: why complicate it? (Dimitri DeFigueiredo)
3. Re: Definition of last: why complicate it? (Daniel Fischer)
4. Re: Definition of last: why complicate it? (Daniel Fischer)
5. Re: Data type definition for a list of elements of
alternating types? (Tony Morris)
6. iterated function value sequence (John M. Dlugosz)
7. Re: iterated function value sequence (Bob Ippolito)
----------------------------------------------------------------------
Message: 1
Date: Fri, 4 Apr 2014 20:26:32 +0100
From: Rudy Matela <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Definition of last: why complicate
it?
Message-ID:
<CALCD0B8qZQYj7vTtqe1dpha2yGRk4=oxd1u9zmdx4bxjqse...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
You can test the speed in your ghci:
-- pretty last
plast :: [a] -> a
plast [x] = x
plast (_:xs) = plast xs
plast [] = error "empty list!"
-- ugly last
ulast :: [a] -> a
ulast [] = error "empty list!"
ulast (x:xs) = ulast' x xs
where ulast' y [] = y
ulast' _ (y:ys) = ulast' y ys
Not a big difference tough:
ghci> :set +s
ghci> ulast [1..20000000]
20000000
(2.59 secs, 2721962752 bytes)
ghci> plast [1..20000000]
20000000
(2.70 secs, 2401902096 bytes)
*Main>
However, if you disable optimization (ghci -O0), the difference is more clear:
ghci> ulast [1..20000000]
20000000
(2.56 secs, 2729847944 bytes)
ghci> plast [1..20000000]
20000000
(3.30 secs, 2401899840 bytes)
On Fri, Apr 4, 2014 at 8:12 PM, Rudy Matela <[email protected]> wrote:
> Hi,
>
> Basically the second one should be faster. I'm *guessing* here as
> *I'm no Haskell wizard*, so someone correct me if I'm wrong.
>
>
> In the first version, at each iteraction (applying to a non-empty
> list), the program will:
>
> 1. Check for a non-empty list, with one element -- return x if true
> *then*
> 2. Check for a non-empty list -- do something to the tail if true
>
> So basically, at each iteration you're doing two "check operations",
> and you know that the first operation will be true only for the last
> element which is wasteful. On a array with 10 elements you do roughly
> 19 "check operations" (2n - 1).
>
>
> In the second version:
>
> 0. Check for empty list error (you only do that once) because the
> recursion is on last'
> then, for each element:
> 1. check wether the passes list is empty (1 check) -- return y if
> true, apply recursion if false
>
> On a array with 10 elements you'll do roughly 11 "check operations" (n+1).
>
>
> According to a stackoverflow answer [1], this should be done
> automatically by GHC. Why it's still defined like that I don't know:
> maybe because the code is for when using other compilers, or maybe I
> misinterpreted the stackoverflow post and GHC is not able to do that.
>
>
> [1]: https://stackoverflow.com/a/12661937, under "Case Expressions"
>
>
> Regards,
> Rudy
>
> On Fri, Apr 4, 2014 at 7:17 PM, Dimitri DeFigueiredo
> <[email protected]> wrote:
>> I was looking at the definition of last in the prelude and saw this code
>>
>> (from
>> http://hackage.haskell.org/package/base-4.2.0.1/docs/src/GHC-List.html)
>>
>> -- | Extract the last element of a list, which must be finite and non-empty.
>> last :: [a] -> a
>> #ifdef USE_REPORT_PRELUDE
>> last [x] = x
>> last (_:xs) = last xs
>> last [] = errorEmptyList "last"
>> #else
>> -- eliminate repeated cases
>> last [] = errorEmptyList "last"
>> last (x:xs) = last' x xs
>> where last' y [] = y
>> last' _ (y:ys) = last' y ys
>> #endif
>>
>> Question: What does the second "eliminate repeated cases" definition of last
>> gain compared to the first (simpler) one?
>>
>> Thanks
>>
>> Dimitri
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Message: 2
Date: Fri, 04 Apr 2014 13:51:42 -0600
From: Dimitri DeFigueiredo <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Definition of last: why complicate
it?
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
I think that in the second case (ulast' in your test) still performs 2
checks per iteration as it has to check for the empty list on its second
argument at every recursive call (that's how it knows it's done). So, we
are performing the same number of iterations. Maybe there's another
reason for the "ugly" version to be preferred. Even if it is
performance and not lazyness, I still don't understand what would make
it faster.
Thanks,
Dimitri
Em 04/04/14 13:26, Rudy Matela escreveu:
> You can test the speed in your ghci:
>
>
> -- pretty last
> plast :: [a] -> a
> plast [x] = x
> plast (_:xs) = plast xs
> plast [] = error "empty list!"
>
> -- ugly last
> ulast :: [a] -> a
> ulast [] = error "empty list!"
> ulast (x:xs) = ulast' x xs
> where ulast' y [] = y
> ulast' _ (y:ys) = ulast' y ys
>
>
> Not a big difference tough:
> ghci> :set +s
> ghci> ulast [1..20000000]
> 20000000
> (2.59 secs, 2721962752 bytes)
> ghci> plast [1..20000000]
> 20000000
> (2.70 secs, 2401902096 bytes)
> *Main>
>
>
> However, if you disable optimization (ghci -O0), the difference is more clear:
> ghci> ulast [1..20000000]
> 20000000
> (2.56 secs, 2729847944 bytes)
> ghci> plast [1..20000000]
> 20000000
> (3.30 secs, 2401899840 bytes)
>
>
>
> On Fri, Apr 4, 2014 at 8:12 PM, Rudy Matela <[email protected]> wrote:
>> Hi,
>>
>> Basically the second one should be faster. I'm *guessing* here as
>> *I'm no Haskell wizard*, so someone correct me if I'm wrong.
>>
>>
>> In the first version, at each iteraction (applying to a non-empty
>> list), the program will:
>>
>> 1. Check for a non-empty list, with one element -- return x if true
>> *then*
>> 2. Check for a non-empty list -- do something to the tail if true
>>
>> So basically, at each iteration you're doing two "check operations",
>> and you know that the first operation will be true only for the last
>> element which is wasteful. On a array with 10 elements you do roughly
>> 19 "check operations" (2n - 1).
>>
>>
>> In the second version:
>>
>> 0. Check for empty list error (you only do that once) because the
>> recursion is on last'
>> then, for each element:
>> 1. check wether the passes list is empty (1 check) -- return y if
>> true, apply recursion if false
>>
>> On a array with 10 elements you'll do roughly 11 "check operations" (n+1).
>>
>>
>> According to a stackoverflow answer [1], this should be done
>> automatically by GHC. Why it's still defined like that I don't know:
>> maybe because the code is for when using other compilers, or maybe I
>> misinterpreted the stackoverflow post and GHC is not able to do that.
>>
>>
>> [1]: https://stackoverflow.com/a/12661937, under "Case Expressions"
>>
>>
>> Regards,
>> Rudy
>>
>> On Fri, Apr 4, 2014 at 7:17 PM, Dimitri DeFigueiredo
>> <[email protected]> wrote:
>>> I was looking at the definition of last in the prelude and saw this code
>>>
>>> (from
>>> http://hackage.haskell.org/package/base-4.2.0.1/docs/src/GHC-List.html)
>>>
>>> -- | Extract the last element of a list, which must be finite and non-empty.
>>> last :: [a] -> a
>>> #ifdef USE_REPORT_PRELUDE
>>> last [x] = x
>>> last (_:xs) = last xs
>>> last [] = errorEmptyList "last"
>>> #else
>>> -- eliminate repeated cases
>>> last [] = errorEmptyList "last"
>>> last (x:xs) = last' x xs
>>> where last' y [] = y
>>> last' _ (y:ys) = last' y ys
>>> #endif
>>>
>>> Question: What does the second "eliminate repeated cases" definition of last
>>> gain compared to the first (simpler) one?
>>>
>>> Thanks
>>>
>>> Dimitri
>>> _______________________________________________
>>> Beginners mailing list
>>> [email protected]
>>> http://www.haskell.org/mailman/listinfo/beginners
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Message: 3
Date: Fri, 04 Apr 2014 21:53:17 +0200
From: Daniel Fischer <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Definition of last: why complicate
it?
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
On Friday 04 April 2014, 20:12:50, Rudy Matela wrote:
> According to a stackoverflow answer [1], this should be done
> automatically by GHC. Why it's still defined like that I don't know:
> maybe because the code is for when using other compilers, or maybe I
> misinterpreted the stackoverflow post and GHC is not able to do that.
One can check that, just copy the source (hiding Prelude.last or renaming it)
and compile, with -ddump-simpl to get the core GHC produces (it takes a little
practice to read core, but it's sufficiently similar to Haskell to start
understanding much of it quickly).
With -O2, all GHC versions I tried (6.12.3, 7.0.2, 7.2.2, 7.4.2, 7.6.1, 7.6.3)
produced (almost?) the more efficient version from the USE_REPORT_PRELUDE
source, but with only -O, none did.
If the libraries are guaranteed to be compiled with -O2 when building the
compiler, there would be no need for the other source. But since that is not
guaranteed, it's better to manually write the better version.
Footnote (?): what GHC produces with -O2 is slightly different, it tests for a
singleton list once in the wrapper before the worker is called, but it also
creates a rule that when it is called on a list that is known at compile-time
to be nonempty, the worker shall be called directly.
Cheers,
Daniel
------------------------------
Message: 4
Date: Fri, 04 Apr 2014 22:01:19 +0200
From: Daniel Fischer <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Definition of last: why complicate
it?
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
On Friday 04 April 2014, 13:51:42, Dimitri DeFigueiredo wrote:
> I think that in the second case (ulast' in your test) still performs 2
> checks per iteration as it has to check for the empty list on its second
> argument at every recursive call (that's how it knows it's done). So, we
> are performing the same number of iterations.
But in each iteration, there is only one case, versus the two in the plast
version, we have
ulast' y ys = case ys of
[] -> y
z:zs -> ulast' z zs
> Maybe there's another
> reason for the "ugly" version to be preferred. Even if it is
> performance and not lazyness, I still don't understand what would make
> it faster.
>
> Thanks,
>
> Dimitri
>
> Em 04/04/14 13:26, Rudy Matela escreveu:
> > You can test the speed in your ghci:
No.
ghci is not a measure for efficiency of code. You need compiled (with
optimisations) code to be able to judge and compare efficiency. Even when
loading compiled and optimised code in ghci, ghci's runtime still behaves
different from the runtime of the compiled code in binaries.
To check the efficiency of code, ghc -O2 and the criterion library are your
friends.
Cheers,
Daniel
------------------------------
Message: 5
Date: Sat, 5 Apr 2014 09:19:27 +1300
From: Tony Morris <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Data type definition for a list of
elements of alternating types?
Message-ID:
<CAJf6Usg44N0mw24r2y3uxmSbsMf=y0uta_zkf5-fx6h4apo...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
See the separated package on hackage.
On 03/04/2014 2:53 PM, "Jacek Dudek" <[email protected]> wrote:
> -- As an exercise I wanted to define a datatype that is an alternating
> list of elements of two different types. The best that I could do are
> the type definitions below:
>
> module BiList
> ( BiList (..)
> , AList (EmptyA)
> , BList (EmptyB)
> ) where
>
> data BiList a b
> = Empty
> | BA (AList a b)
> | BB (BList a b)
>
> data AList a b
> = EmptyA
> | AL a (BList a b)
>
> data BList a b
> = EmptyB
> | BL b (AList a b)
>
> (<#) :: a -> (BList a b) -> (AList a b)
> a <# bs = AL a bs
>
> (<@) :: b -> (AList a b) -> (BList a b)
> b <@ as = BL b as
>
> infixr 5 <#
> infixr 5 <@
>
> example :: BiList Int Char
> example = BA $ 1 <# 'a' <@ 2 <# 'b' <@ 3 <# 'c' <@ 4 <# 'd' <@ EmptyA
>
> -- There are two things that I don't like about this implementation.
>
> -- (1) The BA and BB constructors that must be applied on top of
> instances of (AList a b) and (BList a b) to lift them to be of type
> (BiList a b).
>
> -- (2) Having three different constructors for an empty list: Empty,
> EmptyA, EmptyB, where ideally I would just have one.
>
> -- Is it possible to get around either of these annoyances with some
> type theory gymnastics? Maybe something like the function fromIntegral
> (the mechanics of which I don't really understand at this point)?
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140405/5b09e6a9/attachment-0001.html>
------------------------------
Message: 6
Date: Fri, 04 Apr 2014 15:25:25 -0500
From: "John M. Dlugosz" <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] iterated function value sequence
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8; format=flowed
What's a good way to produce an iterated function value sequence? That is,
f(x), f(f(x)),
f(f(f(x))), etc.
ref: https://www.youtube.com/watch?v=09JslnY7W_k
------------------------------
Message: 7
Date: Fri, 4 Apr 2014 13:35:50 -0700
From: Bob Ippolito <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] iterated function value sequence
Message-ID:
<cacwmpm9d2xyeytw04tulquvbwnkafdkxu00a9qqt5fcb6b-...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
There's a function named iterate in Prelude:
?> :info iterate
iterate :: (a -> a) -> a -> [a] -- Defined in `GHC.List'
?> take 8 (iterate (\x -> 2 * x + 1) 0)
[0,1,3,7,15,31,63,127]
On Fri, Apr 4, 2014 at 1:25 PM, John M. Dlugosz <[email protected]>wrote:
> What's a good way to produce an iterated function value sequence? That
> is, f(x), f(f(x)), f(f(f(x))), etc.
>
> ref: https://www.youtube.com/watch?v=09JslnY7W_k
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140404/d2e1f65d/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 70, Issue 8
****************************************
