Practice meeting, Dec. 16th

[Lyle Kopnicky]

When: Monday, Dec 16h, 6:30-8:30pm

Where: Collective Agency Downtown, Suite 1108, 511 SW 10th Ave, Portland, OR (opposite side of the floor from the elevators)

We'll discuss the rest of chapter Chapter 14, "Distributed Programming", of Parallel and Concurrent Programming in Haskell, starting with the section "Merging Channels" on p. 257. Please read it beforehand. You may wish to try running the code examples from the book. At the meeting anyone will be able to present and contribute to the discussion.

Meetup link to RSVP:

https://www.meetup.com/Portland-Functional-Programming-Study-Group/events/dcgwjryzqbvb/

Hope to see you then!

[Lyle Kopnicky]

Good meeting!

TJ asked about how to do something like a fixed point, but of a function that takes multiple parameters. We discussed it a bit, but I want to write up a fuller answer in another email.

We got through most of the rest of the chapter, but kind of left off in the section on "Failure and Adding/Removing Nodes". That section proposes an extension to allow us to add/remove nodes at will.

I suggest that for next time we try implementing that extended version. For comparison, there is already a solution in the source repo: distrib-chat/chat-noslave.hs.

We should also try writing the key/value store mentioned in the last section!

Happy Holidays,

Lyle

[Lyle Kopnicky]

In the meeting, we had some questions about how some of the type class instance declarations worked. I've looked into it and now have some explanations:

    data Message = Ping ProcessId | Pong ProcessId
        deriving (Typeable, Generic)

    instance Binary Message

We wondered, how is it that we can declare an instance of Binary for Message, without any code? Surely there are some methods to be filled in.

It turns out that yes, Binary has methods put and get that need to be defined. But it has default definitions for those methods. Those default definitions rely on additional type constraints, a feature enabled by the DefaultSignatures extension.

    default put :: (Generic t, GBinaryPut (Rep t)) => t -> Put
    put = gput . from

    default get :: (Generic t, GBinaryGet (Rep t)) => Get t
    get = to `fmap` gget

So, as long as you have an instance Generic Message (which we have derived) and instances of GBinaryPut (Rep Message) and GBinaryGet (Rep Message), then you will get those methods for free.

We get Rep Message from the Typeable instance - it's an associated type family. There are Binary instances for base types defined in Data.Binary.Class. And there are instances of Binary in in Data.Binary.Generic which work on type reps for custom types, and rely on the instances for the base types.

As for the other mysterious instance:

    class (Binary a, Typeable a) => Serializable a

    instance (Binary a, Typeable a) => Serializable a

Turns out that's not so mysterious, and basically does what it looks like. When a function is defined with Serializable as a constraint, it will resolve to that instance, and then check to see that the constraints are satisfied - if not, it will give an error.

Why are there no methods for this class? Instead, there are standalone functions with the Serializable constraint, that make use of the methods of Binary and Typeable. As long as the Serializable constraint is satisfied, then we know the constraints for Binary and Typeable must be satisfied, too, so that works.

It could have alternately been defined with Serializable being a constraint kind:

    type Serializable a = (Binary a, Typeable a)

The difference there is that it wouldn't be possible to define custom instances of Serializable. You can't make an instance for something that's not a class.

- Lyle

--
You received this message because you are subscribed to the Google Groups "pdxfunc" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pdxfunc+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/pdxfunc/f7877321-c891-45ed-a449-bb545a93061d%40googlegroups.com.

[Lyle Kopnicky]

TJ, here are some (increasingly fast) solutions I came up with to the problem of computing a binomial coefficient:

https://gist.github.com/lylek/90e2b091407b1204fac479419777907c

Exactly what algorithm is best depends on the context. Are you going to be repeatedly computing the same coefficients, so that it would be beneficial to use some space to cache the results? Perhaps you need to calculate all the coefficients for a particular n, with different k?

In my solutions I assumed that you just want to compute a single coefficient.

The first solution is the naïve recursive solution that does sums. It's quite slow.

The second solution computes a list of lists of the coefficients - a lazy Pascal's triangle. Then it indexes into the lists according to the coordinates you selected. Unlike the recursive solution, it never has to recompute any entries, during that call. If you call it again, it starts from scratch. But if you wanted to cache the results, you can just have it return the table instead of the individual results. It's not super-efficient at lookup because it's a list of lists. That could be addressed by using vectors instead of lists. It would have to be tuned to your use case.

The third solution uses a mathematical shortcut - calculating the results using products instead of sums. It's very fast.

In fact, the only real reason to use the tabular method is if you want to cache results.

- Lyle

[Lyle Kopnicky]

There's apparently another mathematical trick. You can calculate the binomial coefficient using only a diagonal of Pascal's triangle.

https://stackoverflow.com/questions/28896626/tail-recursive-binomial-coefficient-function-in-haskell

It's not any more efficient than my third solution, but it's interesting.

- Lyle

[Lyle Kopnicky]

There's also this library that purports to have a very fast implementation:

https://hackage.haskell.org/package/combinatorics-0.1.0/docs/Math-Combinatorics-Binomial.html