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: Get max element of a list using foldl or foldr
(Andrew Bernard)
2. Re: Optimising a combinatorial algorithm? (Bernhard Herzog)
3. Re: foldl on Bool:s (goforgit .)
----------------------------------------------------------------------
Message: 1
Date: Sat, 26 Sep 2015 09:59:13 +1000
From: Andrew Bernard <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Get max element of a list using foldl
or foldr
Message-ID: <[email protected]>
Content-Type: text/plain; charset="UTF-8"
Hi JAMB,
If I just show an answer if defeats the purpose of the exercise, but just use
max in a lambda function for the fold.
But, you need to consider what the maximum of an empty list is. Since it is
hard to say what it may be, may I suggest you return a Maybe value for your
function, and don?t forget to cover the case of the empty list [].
Andrew
------------------------------
Message: 2
Date: Sat, 26 Sep 2015 16:55:05 +0200
From: Bernhard Herzog <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Optimising a combinatorial algorithm?
Message-ID: <[email protected]>
Content-Type: Text/Plain; charset="utf-8"
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.
The type Voice can obviously be treated in a similar way.
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.
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.
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.
Some stylistic things:
instance Duration Measure where
dur m = case m of [] -> Nothing; otherwise -> dur (head m)
would better be written like this:
instance Duration Measure where
dur [] = Nothing
dur (x:_) = dur x
I.e. try not to use head. Use pattern matching instead. Particularly in
cases like this, where you already pattern match on the list in
question. This applies to some other functions as well, e.g. allEqDur.
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.
If you compile your code with GHC's -Wall option it warns about this and
other things.
Bernhard
------------------------------
Message: 3
Date: Sun, 27 Sep 2015 10:28:50 +0200
From: "goforgit ." <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] foldl on Bool:s
Message-ID:
<CAHzzbMDCO0xKMOuXSXUYyA_0Hb3r6PBveoQFjfh7W1ZXsb=0...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Interesting, I did not know that, thank you!
On Sat, Sep 26, 2015 at 12:16 AM, Rein Henrichs <[email protected]>
wrote:
> Note that you would like the elem function to stop at the matching element
> and return True rather than checking the rest of the list needlessy, which
> can be done with foldr but not with foldl. The actual implementation of
> elem does this, so you can say:
>
> > elem 1 [1..]
> True
>
> which would fail to terminate with the foldl version.
>
> On Fri, Sep 25, 2015 at 11:10 AM goforgit . <[email protected]> wrote:
>
>> Thanks I got it now :)
>>
>> On Thu, Sep 24, 2015 at 9:45 PM, Kostiantyn Rybnikov <[email protected]>
>> wrote:
>>
>>> Hi.
>>>
>>> Your function gets passed numbers one by one in the place of x, and its
>>> previous result in the place of acc, and it returns a Bool. Initial value
>>> in place of acc parameter ("previous result") is put as False (since you
>>> begin with answer "no" to question "is it elem?").
>>>
>>> Hope this helps.
>>> 24 ???. 2015 19:04 "goforgit ." <[email protected]> ????:
>>>
>>>> Reading http://learnyouahaskell.com/higher-order-functions
>>>>
>>>> I understand that with the function
>>>>
>>>> sum' :: (Num a) => [a] -> a
>>>> sum' = foldl (+) 0
>>>>
>>>> the call
>>>>
>>>> ghci>>> sum' [1,2,3]
>>>>
>>>> will be evaluated as
>>>>
>>>> 0 + 1 + 2 + 3 = 6
>>>>
>>>> But what about the function
>>>>
>>>> elem' :: (Eq a) => a -> [a] -> Bool
>>>> elem' y ys = foldl (\acc x -> if x == y then True else acc) False ys
>>>>
>>>> and calling it with
>>>>
>>>> ghci>>> elem' 3 [1,2,3]
>>>>
>>>> How is that evaluated to True by foldl in elem'?
>>>>
>>>> Thanks in advance for any explanation to this!
>>>>
>>>> _______________________________________________
>>>> 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
>>>
>>>
>> _______________________________________________
>> 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/20150927/da21cf91/attachment-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 87, Issue 19
*****************************************
