Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/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: Optimising a combinatorial algorithm? (Mario Lang)
2. Help with a data type declaration ([email protected])
3. Re: Help with a data type declaration (emacstheviking)
4. Re: Help with a data type declaration (emacstheviking)
5. Re: Help with a data type declaration (David McBride)
6. Re: Help with a data type declaration (Karl Voelker)
----------------------------------------------------------------------
Message: 1
Date: Tue, 29 Sep 2015 15:37:43 +0200
From: Mario Lang <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Optimising a combinatorial algorithm?
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
Bernhard Herzog <[email protected]> writes:
> On 24.09.2015, Mario Lang wrote:
>> TL;DR: My implementation looks elegant (to me), but is rather slow
>> compared to a well optimized C++ impl. of the same algorithm. Runtime
>> differences are currently huge. Looking for input on what I could
>> change to match C++ performance, without loosing too much expressiveness
>> of the code.
> [...]
>> Profiling tells me I am spending 90% of all the time in 'dur', which is my
>> small helper method to calculate the duration of a PartialVoice,
>> PartialMeasure or Voice.
>>
>> The project is setup to support profiling:
>>
>> git clone https://github.com/mlang/hbmc
>> cd hbmc
>> cabal run profiling
>
> Some performance tips:
>
> AFAICT, the main reason the dur methods are so slow is they traverses
> the lists much too often. An easy way to reduce that number is to cache
> the duration of lists of Sign values in PartialVoice by replacing the
> type alias with a new data type like this:
>
> data PartialVoice = PV (Maybe Rational) [Sign]
>
> To always initialize the duration when constructing a PartialVoice, a
> helper function is useful:
>
> mkPV signs = PV (sumDuration signs) signs
>
> Here sumDuration is defined in the same way as the current dur method
> for PartialVoice:
>
> sumDuration :: Duration a => [a] -> Maybe Rational
> sumDuration = foldl' (liftA2 (+)) (pure 0) . map dur
>
> The dur method for PartialVoice can then be implemented by simply
> accessing the cached value:
>
> instance Duration PartialVoice where
>
> dur (PV d _) = d
>
> Since that parameter of PV is lazy the actual sum is only computed when
> the value is needed and for any given PV value it is computed at most
> once.
>
> On my system, that change alone improved the running time by a factor of
> almost 10 according to the profiler output.
Confirmed (committed). Thanks a lot! This indeed brought a factor of 10
speedup.
I wonder why the attempts to memoize dur by other people did not help at
all.
After all, this is just another type of memoisation, isn't it?
> Some other changes that can improve the speed:
>
> Use Integer instead of Rational.
>
> This should be possible since all duration values appear to be integer
> multiples of 1/128, so you can just represent them by that factor and
> use a newtype wrapper for increased type safety.
I will eventually have to deal with musical tuplets, so it is not just
128th values. I see your point, but I am going to delay that
optimisation until I know I really need it.
> Parameterize Sign with the type of the duration.
>
> AFAICT the only reason to wrap the duration in a Maybe is that you
> cannot assign a duration during parsing, so the parsers always assign
> Nothing as duration. The pvs function will always assign a Just-value to
> each Sign, however. So after parsing, the Measure has Nothing for the
> duration in every Sign, but the Measures returned by ms always have Just
> values. You you could express this in the types by parameterizing Sign
> and the other types with the type of a duration. The parser would then
> create e.g. Sign () values and pvs would turn those into e.g. Sign
> Rational values.
That is a good idea I was already thinking about.
Actually, what I am trying to figure out is how to do closely related,
but different, datatypes in Haskell. In C++, I am used to being able to
inherit from an existing class, just adding the new fields I need. This
works without name clashes obviously because two classes can have the
same field names without clashing. However, I am missing something like
this from Haskell.
What I actually need in the long run, is a separate data type
for every enhancement step in my post-processing. I current have
AmbiguousSign and Sign. However, I will need more types like this, with
every step, I'd like to add yet another field, which is going to be
computed by that step.
AFAIU the parametrisation trick you mention above works for a single field.
How would I go about progressively adding more and more fields to a base
data type?
> This improves type safety, makes the meaning clearer and simplifies the
> code because you don't need to lift operations into the Maybe or do case
> analyses.
I agree. Doing away with the Maybe was a good thing.
> Also, if you want to ignore parts of a pattern match, use "_" as the
> pattern, not "otherwise". In the way you used it, it introduces a new
> binding in that branch of the case expression and shadows the definition
> from the Prelude. Idiomatic use of "otherwise" is as the condition on
> the catch-all case of a guard.
Oh, thanks for pointing that out, I didn't realize at all that otherwise
doesn't work like expected in "normal" case expressions.
--
CYa,
?????
------------------------------
Message: 2
Date: Tue, 29 Sep 2015 09:10:48 -0500
From: [email protected]
To: [email protected]
Subject: [Haskell-beginners] Help with a data type declaration
Message-ID: <[email protected]>
Content-Type: text/plain; charset=US-ASCII; format=flowed
How can I interpret the following data type declaration? The book where
I am studying (and other sources I have read as well) only show more
simple examples. This is what I can say about it:
* "Tree" is the name of the new type.
* "Branch" and "Leaf" are the type constructors.
* What is "a" and "b"?
* It seems to me that this type is kind of "recursively" defined but I
do not know exactly.
data Tree a b = Branch b (Tree a b) (Tree a b)
| Leaf a
I will very much appreciate your feedback.
Regards,
JAMB
------------------------------
Message: 3
Date: Tue, 29 Sep 2015 16:10:15 +0100
From: emacstheviking <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Help with a data type declaration
Message-ID:
<CAEiEuU+xoTk6Sgky1d1B9H_4qqU=cb==n7aqhasjqbdp6gb...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
a = left b = right
That would at least make the sentiment clearer.
On 29 September 2015 at 15:10, <[email protected]> wrote:
> How can I interpret the following data type declaration? The book where I
> am studying (and other sources I have read as well) only show more simple
> examples. This is what I can say about it:
>
> * "Tree" is the name of the new type.
> * "Branch" and "Leaf" are the type constructors.
> * What is "a" and "b"?
> * It seems to me that this type is kind of "recursively" defined but I do
> not know exactly.
>
>
> data Tree a b = Branch b (Tree a b) (Tree a b)
> | Leaf a
>
> I will very much appreciate your feedback.
>
> Regards,
> JAMB
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150929/aff85b44/attachment-0001.html>
------------------------------
Message: 4
Date: Tue, 29 Sep 2015 16:10:56 +0100
From: emacstheviking <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Help with a data type declaration
Message-ID:
<caeieuulwp2hvgh7y8cs3dru0uwh98cqo8n9ng6xvauvkkpm...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Is the definition of Branch correct though, shouldn't it be Branch (Tree a
b) (Tree a b) ...?
On 29 September 2015 at 16:10, emacstheviking <[email protected]> wrote:
> a = left b = right
>
> That would at least make the sentiment clearer.
>
>
>
> On 29 September 2015 at 15:10, <[email protected]> wrote:
>
>> How can I interpret the following data type declaration? The book where I
>> am studying (and other sources I have read as well) only show more simple
>> examples. This is what I can say about it:
>>
>> * "Tree" is the name of the new type.
>> * "Branch" and "Leaf" are the type constructors.
>> * What is "a" and "b"?
>> * It seems to me that this type is kind of "recursively" defined but I do
>> not know exactly.
>>
>>
>> data Tree a b = Branch b (Tree a b) (Tree a b)
>> | Leaf a
>>
>> I will very much appreciate your feedback.
>>
>> Regards,
>> JAMB
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150929/af5c94b3/attachment-0001.html>
------------------------------
Message: 5
Date: Tue, 29 Sep 2015 11:22:37 -0400
From: David McBride <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Help with a data type declaration
Message-ID:
<CAN+Tr43jzPEnog3hp=RVsyjx0539ME_uwFD_h-AP23=m4_+...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
It just stores a 'b' on every branch and an 'a' on every leaf. I'm not
sure what you'd use it for, but there's nothing wrong with it.
On Tue, Sep 29, 2015 at 11:10 AM, emacstheviking <[email protected]> wrote:
> Is the definition of Branch correct though, shouldn't it be Branch (Tree a
> b) (Tree a b) ...?
>
>
> On 29 September 2015 at 16:10, emacstheviking <[email protected]> wrote:
>
>> a = left b = right
>>
>> That would at least make the sentiment clearer.
>>
>>
>>
>> On 29 September 2015 at 15:10, <[email protected]> wrote:
>>
>>> How can I interpret the following data type declaration? The book where
>>> I am studying (and other sources I have read as well) only show more simple
>>> examples. This is what I can say about it:
>>>
>>> * "Tree" is the name of the new type.
>>> * "Branch" and "Leaf" are the type constructors.
>>> * What is "a" and "b"?
>>> * It seems to me that this type is kind of "recursively" defined but I
>>> do not know exactly.
>>>
>>>
>>> data Tree a b = Branch b (Tree a b) (Tree a b)
>>> | Leaf a
>>>
>>> I will very much appreciate your feedback.
>>>
>>> Regards,
>>> JAMB
>>> _______________________________________________
>>> Beginners mailing list
>>> [email protected]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>
>>
>>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150929/45403e79/attachment-0001.html>
------------------------------
Message: 6
Date: Tue, 29 Sep 2015 08:27:59 -0700
From: Karl Voelker <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Help with a data type declaration
Message-ID:
<1443540479.2900266.396621081.1261a...@webmail.messagingengine.com>
Content-Type: text/plain
On Tue, Sep 29, 2015, at 07:10 AM, [email protected] wrote:
> * "Tree" is the name of the new type.
> * "Branch" and "Leaf" are the type constructors.
> * What is "a" and "b"?
"Tree" is not quite the name of a type. It is the name of a type
constructor - in other words, it is a "type-level function". This also
explains "a" and "b" - they are the parameters to the type constructor
(which means they are "type variables").
To get a type, you have to apply the type constructor. So, for example,
"Tree Char Int" is a type.
"Branch" and "Leaf" are not type constructors - they are *data*
constructors.
> * It seems to me that this type is kind of "recursively" defined but I
> do not know exactly.
Yes. It's recursive because a value of type "Tree a b" can be built up
from other values of type "Tree a b" (if you use the "Branch"
constructor).
-Karl
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 87, Issue 20
*****************************************
