BarCamp, Yoda and unfolding

I've been trying to work out a good narrative for doing a version of Yoda speaks Visual Haskell at BarCamp next week. The (a?) problem is that experienced functional programmers won't get much out of it, and maybe those who would be interested in an introduction will be put off thinking it will get too complex — from zero to monads in 25 minutes would be too hair raising.

My first thought was that I would use the interactive GHCi and develop the whole thing just using that and a flip chart or whiteboard to explain a few of the core concepts. Basically I just want to get across a feel for how map and fold are used.

To this end I was fiddling around yesterday trying to work out what order to introduce the parts of the program in and how to tie them together in such a way that people wouldn't get too lost. In doing this I was wondering how to deal with the inner_duplicate function.

inner_duplicate ( first : second : [] ) = [ ( first, second ) ]
inner_duplicate ( first : second : the_rest ) = ( first, second) : ( inner_duplicate ( second : the_rest ) )

It's the only function which requires two clauses which I think makes it useful instructionally, but very awkward on the command line as it has to be entered as a single clause.

let inner_duplicate ( first : second : [] ) = [ ( first, second ) ]; inner_duplicate ( first : second : the_rest ) = ( first, second) : ( inner_duplicate ( second : the_rest ) )

That seems like it's just going to be too long to do in a short talk given the other concepts that I want to get across. I think this means I will probably end up using Visual Haskell anyway, which might not be such a bad thing.

And unfolding?

In playing around with this I was starting to wonder about other ways of doing it. It's not a very complex bit of list processing but I couldn't find any library function using Hoogle¹ [1Something else I'm not going to be able to show as the entire BarCamp will be running on a single ADSL connection so having something in a talk that requires internet access is not a smart move.] that looked like it might do it.

It is however a fairly obvious thing for a generator to do. I think you can probably do it with a fold in some way, but I wanted to have a play with the unfold functions. A few type errors later and I'd come up with this:

let words = [ "fear", "anger", "hate", "suffering" ]
unfoldr (\x -> if length x < 2 then Nothing else Just ( (head x, (head $ tail x)),(tail x) ) ) words

Which gives the right output:

[("fear","anger"),("anger","hate"),("hate","suffering"),("suffering","pain")]

This morning when I came back to it I was thinking that this use of the Maybe monad is kind of clever in its own way, but I was wondering why it was there at all. Given a Y Combinator you should be able to do it something like this instead (let's call it unfoldy for unfold Y combinator):

unfoldy (\x f -> if length x < 2 then [] else ( (head x, (head $ tail x)) : ( f $ tail x ) ) ) words

I don't really know whether it is better or not, probably just different. I also haven't spent any time thinking about how you'd go about implementing unfoldy. The implementation with the Maybe monad might be easier to understand, or just more obvious in some way. Personally I find the unfoldy easier to read, but that's probably because it more closely follows the function I started with.

In any case, once you start down this road you realise that it can all be simplified a lot more. Here's another version of the function:

let inner_duplicate = (\x -> if length x < 2 then [] else ( (head x, (head $ tail x)) : ( inner_duplicate $ tail x ) ) )

This avoids the unfold completely, but it has to repeat the function name inside the definition. This is exactly the problem that the Y combinator solves. Here's a version that uses it:

let inner_duplicate = fix (\f x -> if length x < 2 then [] else ( (head x, (head $ tail x)) : ( f $ tail x ) ) )

This is short enough to enter in GHCi, but I expect that the concepts might be too hard. Maybe it can be used as a teaser… Something I'll have to think about.