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. Dynamic programming (memoization) w/ string keys. (Sourabh)
2. Re: grouping functions together (Dimitri DeFigueiredo)
3. Re: parallel map/filter (Csaba Marosi)
----------------------------------------------------------------------
Message: 1
Date: Mon, 8 Jun 2015 20:54:38 -0700
From: Sourabh <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] Dynamic programming (memoization) w/
string keys.
Message-ID:
<CAK0HM3=aue7gmvvi2en-khaoxq17vtnk7khyyq0-hsxy2vr...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
I haven't tried in another language yet. I wasn't aware of nim-sum, and
looked up the game of nim. And yes, this sounds like a tweak on the nim
problem, so I will take a look at game theory. Thank you for the pointers.
Coursera has a course on combinatorial game theory, and I've put it on my
watch list now!
I'll try to tweak my program to use bits instead of strings. I don't think
I've ever used bit shifting in Haskell (I've used it plenty in C), so it
should be interesting.
Thanks for the suggestions Stefan!
> Do you have a dynamic programming solution which runs reasonably fast
> in another language? Because this game of kyles looks like an example
> from combinatoric game theory to me and as such it might be much more
> efficient to solve it using nim-sums (if possible; I haven't given this
> too much thought).
>
> Also note that, since your strings only consist of X and I, you could
> also use Integers and bit-operations instead of lists in your
> algorithms. You'd still need a Map for memoization, but other operations
> might be much faster.
>
> Cheers
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150608/7bce9f3e/attachment-0001.html>
------------------------------
Message: 2
Date: Mon, 08 Jun 2015 22:04:15 -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] grouping functions together
Message-ID: <[email protected]>
Content-Type: text/plain; charset="windows-1252"; Format="flowed"
I used typeclasses because I want to have a "default version" of the run
function.
I want that function to be able to call (specialized versions) of the
other functions in the group. This is the only way *I know* to "factor
out" common code in Haskell while still allowing the "factored out" code
to call specialized versions of the other functions. In my view, this is
very similar to inheritance and specialization is Object-Oriented
Programming. Is there another way to do this?
I don't see how I could do this with a record. If the run function were
mostly the same for all types except for calls to specialized versions
of the others. I think I would have to write a completely separate
version of run for each instance. The example below shows what I mean.
Also, my apologies, but my code was wrong. I now realize it did not
capture what I need. I don't need the functions to be polymorphic for
all types within a single instance. Within a single instance, I just
need them to work for a few specific types. So, here's a better version
(my current one):
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE TypeFamilies #-}
import Control.Monad
class Reliable m s where
type Req s :: * -- the type for requests
type Atp s :: * -- the type for attempts
type Ack s :: * -- the type for acknowledgments
type Res s :: * -- the type for results (Success)
type Fai s :: * -- the type for failures
getRequests :: Monad m => s -> m [Req s]
mkAttempt :: Monad m => s -> Req s -> m (Maybe (Atp s))
action :: Monad m => s -> Atp s -> m (Maybe (Ack s))
getAcks :: Monad m => s ->[Atp s] -> m [Ack s]
mkResult :: Monad m => s -> Req s -> Ack s -> m (Either (Fai s)
(Res s))
run :: Monad m => s -> Req s -> m (Res s)
data RemoteCall = RemoteCall
instance Reliable IO RemoteCall where
type Req RemoteCall = Int
type Atp RemoteCall = String
type Ack RemoteCall = Bool
type Res RemoteCall = String
type Fai RemoteCall = Int
getRequests = undefined -- these can be specialized for each instance
mkAttempt = undefined
action = undefined
getAcks = undefined
mkResult = undefined
run s req = do -- dummy version
mAtp <- mkAttempt s req
mAck <- action s (fromJust mAtp)
eRes <- mkResult s req (fromJust mAck)
return $ case eRes of
Left f -> error "failure"
Right s -> s
I don't know how I would write the 'run' function above only once if I
were using records. It seems I would have to duplicate code, no?
Thank you!
Dimitri
On 08/06/15 16:36, Rein Henrichs wrote:
> This seems like a case where you only really need a record, not a
> typeclass.
>
> On Mon, Jun 8, 2015 at 2:47 PM Dimitri DeFigueiredo
> <[email protected] <mailto:[email protected]>> wrote:
>
> Hello!
>
> I am trying to tie together a group of functions that turn an
> unreliable
> remote network call into a reliable one. For each different network
> request I make, a specific group of these functions should always work
> together, but their type signatures are quite different. My first
> thought was to put them all in a typeclass:
>
> import Control.Monad
>
> class Reliable1 m req attempt ack failure result where
> getRequests1 :: Monad m => m [req]
> mkAttempt1 :: Monad m => req -> m (Maybe attempt)
> action1 :: Monad m => attempt -> m (Maybe ack)
> getAcks1 :: Monad m => [attempt] -> m [ack]
> mkResult1 :: Monad m => req -> ack -> m (Either failure
> result)
> run1 :: Monad m => req -> m result
>
> That doesn't work because not all functions use all parameters. For
> example, getAcks1 has no idea of what the final 'result' type
> parameter
> is. This lead me to my second attempt. Defining a 'service' type with
> the sole purpose of tying them all together. Here's my current
> attempt:
>
> {-# LANGUAGE MultiParamTypeClasses #-}
>
> import Control.Monad
>
> class Reliable m service where
> getReqs :: Monad m => service -> m [req]
> mkAttempt :: Monad m => service -> req -> m (Maybe attempt)
> action :: Monad m => service -> attempt -> m (Maybe ack)
> getAcks :: Monad m => service -> [attempt] -> m [ack]
> mkResult :: Monad m => service -> req -> ack -> m (Either
> failure result)
> run :: Monad m => service -> req -> m result
>
> data RemoteCall = RemoteCall
>
> instance Reliable IO RemoteCall where
> getReqs = undefined
> mkAttempt = undefined
> action = undefined
> getAcks = undefined
> mkResult = undefined
> run = undefined
>
> This works, but I have to explicitly pass the 'service' argument in
> every call.
> Can I avoid passing this parameter every time?
> Question, is there a better way to do this?
> I wanted to have a wrapper to make my remote calls reliable.
>
> Thanks,
>
> Dimitri
>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected] <mailto:[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/20150608/7eec8fec/attachment-0001.html>
------------------------------
Message: 3
Date: Tue, 9 Jun 2015 06:45:06 +0000
From: Csaba Marosi <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] parallel map/filter
Message-ID:
<caej73skarghhm-8y4hadbv0zcv02smb2mb9jjkdjrppyilt...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Thanks for the tips, some comments:
a) I tried to print the list before my expensive map (prints fast) and
even copy-paste the content into the source code, but it did not help.
b) What do you mean by this?
One more question: when I run my program with -s, the stats:
4,961,037,352 bytes allocated in the heap
19,431,024 bytes copied during GC
[...]
3 MB total memory in use (0 MB lost due to fragmentation)
What does the first number (~ 5G memory) mean? When I wrote my
functions, I just assumed that even the bad code will be fast enough.
(Even this question is more about learning that a practical issue.)
Can you recommend any docs about this kind of Haskell internals?
PS: splitting the input file to two, and use bash to wait both half
reduces the runtime by ~40%. What I want here is to annotate my
program with this knowledge to help ghc to beat bash :)
On 6/5/15, Marcin Mrotek <[email protected]> wrote:
> My first guesses would be that:
> a) Your program is slowed down because lines from the file is read one line
> by one, i.e. there's lazy IO at work. Have you tried your code on a list
> that's loaded in the memory as a whole at once?
> b) The cost of dereferencing the next link in a list overwhelms the cost of
> computing one answer. Have you tried using a tree instead?
>
> Best regards,
> Marcin Mrotek
>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 84, Issue 15
*****************************************
