"Thinking in types" or "The mind of a programmer"

[totherme]

In a previous post, pozorvlak and I wondered about the differences between the thought processes that goes into writing good static code, and those that go into good dynamic code. We figured that there wasn't a lot out there to help dynamic programmers get the hang of static style thinking, so what follows is a simple little toy example, solved in what I

Comments

[twanvl]

First of all, a very nice introduction on type based programming!

In your implementation you use foldl, which causes your reverse problems. This happens foldl basicly has a built-in reverse, so you have to undo it afterwards. It is better to use foldr (when in doubt, always use foldr), this gives you

split x = foldr f [[]] where
f z (acc@(y:ys)) = if (z==x) then []:acc
else (z:y):ys

Or maybe using guards instead of if (which is IMO more Haskell like)

split x = foldr f [[]]
where f z (acc@(y:ys))
| z == x = []:acc
| otherwise = (z:y):ys

[totherme]

Thank you :)

Yes, foldr and guards do look better - cheers :)

[anonymous]

Found this off the Planet Haskell blogs. Being fairly new to FP myself, I still don't think much in types, and hadn't really thought of starting with a matching type first then filling in the blanks. I think other beginners might really like some elaboration on the thought process of matching the types up; it took me a few moments to realize first that split was point-free, that split was matching the types from the right, that the 'y' parameter was needed to fill in the second parameter of foldl to make the types perfectly fit, etc.

Then there was the natural tendency for me to want to make the polymorphic type names correspond to each other; things were made easy due to your declaration of split looking like:

split :: b -> [b] -> [[b]]

Which made matching it up with foldl easy by just substituting [[b]] for a and not having to touch b. Whereas the natural tendency would be to write:

split :: a -> [a] -> [[a]]Thus making the substitution in one's head a little trickier for a beginner when looking at foldl. I find that

[anonymous]

Sorry that wasn't as clear as I wanted to make it... I should say I use x/y/z in my types when I'm looking for a match, and then I convert them back to a/b/c afterward. As for "matching from the right", that is to say that split's type matches the right side of foldl.

I also discovered hoogle, which looks fantastic for finding matching types .. though I should probably get good at doing it in my head first. Still, I can't wait for an IDE with built in hooglitude :)

[totherme]

Hoogle is fantastic - and I use it often :)

I think the closest we have to and IDE with built in hooglitude is GHCi on Acid as mentioned here. There's also vim integration, if you want it :)

[totherme]

Thanks - it's nice to know that this stuff is useful to someone :)

I think other beginners might really like some elaboration on the thought process of matching the types up; it took me a few moments to realize first that split was point-free, that split was matching the types from the right, that the 'y' parameter was needed to fill in the second parameter of foldl to make the types perfectly fit, etc.

split sort of came out point free once I'd made the connection between its type signature and the fold one... First, I'll mention the "matching from the right":

In general, I think if you're writing function f such that f :: SomeInputs -> SomeMoreInputs -> AnOutput and you happen to have a function g lying around with type g :: SomeDifferentInputs -> AnOutput then g is a potential candidate for being the last thing called in your definition of f.

As for being point free, if that g has the type g :: SomeDifferentInputs -> SomeMoreInputs -> AnOutput then there's a chance you can make your f point free on SomeMoreInputs - if those

unfolding

[anonymous]

Personally, when I see something like '[b] -> [[b]]', the first thing I think is unfoldr:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

unfoldr takes a seed (in this case, b = [c]), and a function from a seed to an element and a new seed (here, [c] -> Maybe ([c], [c])), and builds a list ([[c]]). The maybe tells it when to stop (end on Nothing, keep going on Just).

Here you'd get, at first:

split c l = unfoldr (f c) l

So you need to find an f that either returns Nothing to stop (at the seed []) or splits off a portion of the seed list otherwise. It so happens an appropriate function is:

f _ [] = Nothing
f c l = let (h, t) = break (==c) l in Just (h, drop 1 t)

So that's another possible way of solving the problem.

Re: unfolding

[totherme]

Ah - unfoldr is one of those things that I've written little toy exercises in, but haven't properly assimilated into my programming yet. Thanks for the pointer - I'll keep an eye out for increasing listeyness in my type signatures in future :)

Re: unfolding

[ari_rahikkala]

(gah. Exhaustion and XHTML don't go well together. I deleted an earlier post of mine here, different in the respect that it had some broken italics elements...)

Anonymous parent poster: Your solution is pretty similar to my hacked-up-in-ghci one, except yours uses unfoldr while mine recurses explicitly (I have not yet attained the level of enlightenment where the former feels more natural than the latter):

split _ [] = [[]];
split at xs = let (this, rest) = break (==at) xs in this : if (null rest) then [] else split at (tail rest)

My process to arrive at this went something like...

let split _ [] = [[]]; split at (x:xs) = if (x == at) then

... wait, what do I put in here? I can't think of a way to say "start a list at this element and then when you get to some certain element end the list" that does not involve a call to a different function that I'd have to... no, actually, I wouldn't need to write it after all, I think it's in the Prelude... span? *checks type* ah, yes, that's the right type, except that what I want actually

Re: unfolding

[totherme]

(a good example of the loose reasoning used in coding here: When I realised that an assumption of mine was wrong, I immediately went on to fix things so that the assumption would be right without actually thinking of whether it has anything to do with how the code is breaking. In this case it was the right thing, not a surprise in a program this short, but in my experience it's usually *not* the right thing to do when working with code that's even slightly more complex)
That interests me

nit

[anonymous]

Your split isn't very lazy. Whenever you are matching against only
one pattern, it's usually a good idea to use irrefutable patterns:

split x = foldr f [[]] where
f z (acc@(~(y:ys))) = if (z==y) then []:acc
else (z:y):ys

This way, you can split infinite lists!

-- Stefan

Re: nit

[totherme]

I hadn't come across irrefutable patterns before - that's very cool, thanks :)

Looks like an unfold to me

[ext_43519]

My thought process would be whenever I see a list type as a result then I think unfold.

b -> [b] -> [[b]]