Posts

No tutorial, I swear...

After grinding through much of the "20 Intermediate Exercises" and just about all of the Monad Challenges, Monads make much more sense to me.

Therefore, I will follow the excellent advice of Stephen Diehl, and will not write a monad-analogy tutorial. Instead, I will say: do the 20 Intermediate Exercises, and take the Monad Challenges. To paraphrase Euclid, there is no royal road to Monads; the exercises and challenges take you down that road at whose end you'll see at least part of why Monads are so useful.

If you were trying to learn group theory and people were standing around you saying "groups are like the integers",  "groups are like Rubik's Cube", "groups are like m x n matrices", "groups are like baryons and mesons", your situation would be much like the student of Haskell amidst all the monad analogy tutorials. In a sense they're backwards. All those things are groups, just as burritos et al. can at least be thought…

Flipping out

I came across the excellent Monad Challenges, a collection of exercises designed to take you through what have become some of the standard example monads and take you through the process that motivates monads as a way to handle these seemingly diverse data structures. Both the Monad Challenges and the 20 Intermediate Exercises are well worth your time. Doing them both is helping me a lot.

That said, they don't quite match up. 20IE's banana is flip bind and apple is flip ap. (This isn't unique; the also excellent Learning Haskell from first principles has as an exercise writing bind in terms of fmap and join, but the declaration it gives has the type of flip bind. The authors do point this out.) As a result, I find myself with something that there's got to be some way to simplify, of the form

foo = flip $ (flip mumble) . (flip frotz)

I'd like to think there's some sort of distributive-like law to be found and used here... watch this space.

Trust in Schönfinkel

I'm working through the "20 Intermediate Exercises" that give Functors and Monads and such cute, non-threatening names and ask you to implement them. I've gotten most of the way through, with three or four that I'm stuck on--that's under the assumption that the inductive step from banana to banana2 will make the rest of the banana<n> obvious. (If you have sausage, it's easy to implement moppy, and vice versa, but avoiding circularity is the issue.)

So... I did a Bad Thing and looked at solutions a couple of people have posted, saying to myself, "OK, I'll look at those I've already done with an eye to more elegant expression, and look at the ones I'm having issues with and make sure I understand"... and came face to face with a question about composition.

<andy_rooney>Didja ever notice that the examples of composition you see are what we think of as functions with one argument?</andy_rooney> Well, one of the solution…

Careful with that infinite list, Eugene...

Warning: this will give away one way to solve a certain low-numbered Project Euler problem.

Any Haskell book, blog, or tutorials you come across has a good chance of including the très élégant Haskell one-liner for an infinite list containing the Fibonacci sequence:

fibs = 0 : 1 : (zipWith (+) fibs (tail fibs))

Thanks to laziness, it will only evaluate out to the last term we actually request... that was, long ago, my downfall. I wanted the terms no bigger than four million, so

filter (<= 4000000) fibs

right? Wrong. You and I know that the Fibonacci sequence is monotonically increasing, but filter doesn't, and it doesn't even notice the particular function we're filtering with to realize it could terminate thanks to monotonicity. So instead,

takeWhile (<= 4000000) fibs

is the way to go.

The particular problem has an additional constraint, because it only wants the even terms of the sequence no bigger than four million. Easy enough to do, just feed it through

filter even

TMTOWTDI, Haskell Style

I assure you there will be no further allusions to Korean earworms. That said, on to the subject at hand...

Remember the exercise in the online Haskell course that had several tests to filter out weak passwords, all of which had to pass for the fictitious system to allow a String value to be used as a password? I wanted to make it easy to change, so I wanted to take a [String -> Bool] and get a [Bool] I could apply and to for the final thumbs up/thumbs down decision.

The first step: roll my own, which has a pleasing symmetry with map if you write it as a list comprehension:

wonkyMap fs x = [f x | f <- fs]

Then I stumbled across Derek Wyatt's blog post about using sequence for the purpose. Life was good... and then I got Haskell Programming from first principles, and life got better, because its authors do a very good job of explaining the Applicative type class. Applicative defines two functions, pure and (<*>):

class Functor f => Applicative f where
    pure  :: a -&g…

Haskell Tool Stack for Ubuntu 16.04

I've upgraded to Ubuntu 16.04 beta 2, and so far, as I've read elsewhere, it's working very nicely.

(One warning: if you have apcupsd installed, turn it off before upgrading! During the upgrade, something happens that causes the UPS battery to look fully discharged, and apcupsd will obligingly shut your system down... in mid-upgrade. Others have seen this when upgrading to 15.10.)

Now I'm reinstalling the various packages I had previously installed, but for FP Complete's Haskell Tool Stack, trying the Ubuntu instructions FP Complete gives (mutatis mutandis for the version) doesn't work, at least as I write. It looks like it's made its way into the Ubuntu repositories, so that sudo apt-get install haskell-stack will do the trick. I'm also quite pleased to see that 16.04 is actually up to date with respect to GHC. ghc --version shows it has 7.10.3. (Now to look to see whether it's up to snuff on the libghc* packages in the repositories...)

A rather long blast from the past about recursion elimination and a bit of complexity theory

While going through old papers, I found something I wrote as a follow-up to an article by Aaron Banerjee in the February 1999 issue of the world of 68’ micros (you can find a somewhat mangled version online here). Both concern recursion elimination, with the well-known “eight queens” problem (place eight queens on a chess board so that none attacks any other) as an example.
I don’t remember whether I submitted it, or whether it was printed. I’m also embarrassed by the barely legible layout—large Helvetica with nearly no leading. To let me toss the printout and keep the text, and to make it easier to read (if only by me), here it is again, with formatting help from LibreOffice and editing for clarity and concision, not to mention fixing bugs I caused by not directly copying and pasting source code. I will come back and fix indentation on the BASIC09 code, after a little experimentation.
Recursion Elimination and the Eight Queens Problem
In the February 1999 the world of 68’ micros, Aaro…