"Thinking in types" or "The mind of a programmer"
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
( Read more... )
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 called break. So, let's see...
let split at [] = [[]]; split at xs = let (this, rest) = break (==at) xs in this : split at rest
break returns a tuple of a "this" part and a "rest" part (I don't want to confuse those with head and tail so I use different nomenclature). I return the "this" part and cons it to recursion on the "rest" part. I've used this pattern before and simply matched the problem to it - no complex thought was involved here. Works so beautifully, too, in lazy languages :).
So let's try it out...
split 1 [1,2,3]
*screen fills with an infinite list of empty lists, I interrupt ghci (and then, by the way, fight for a while with the strange glitchy behaviour that ^C sometimes causes in it)*
Ouch. So what am I doing wrong... hm... well, I'm recursing unconditionally... but if I were calling myself with an empty list I'd hit the first definition and the list would end...
* several minutes pass (hey, I was up all night) before I come to a realisation *
Oh, hm. Let's see what break actually does...
break (==1) [2,3,1,4]
([2,3],[1,4])
Ah, so that's obviously what must be up. I was in the thinking of split, of course, and expecting that break wouldn't return the element that satisfied the predicate. So, I guess I should fix it by taking the tail of the second element before recursing on it (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)
let split _ [] = [[]]; split at xs = let (this, rest) = break (==at) xs in this : split at (tail rest)
split 1 [1,2,3,1,2]
[[],[2,3],[2]*** Exception: Prelude.tail: empty list
Ah, so it's almost right... except... *a few minutes pass again* ah, when rest is an empty list I should just stop recursing there because I can't take the tail of an empty list (and because that means there is no need to recurse any longer anyway - I didn't think of this consciously). I hate introducing conditionals but can't think of any better way to do this...
let split _ [] = [[]]; split at xs = let (this, rest) = break (==at) xs in this : if (null rest) then [] else split at (tail rest)
split 1 [1,2,3,1,2]
[[],[2,3],[2]]
Ah, good. It passed a single test on a list with a couple of elements. Obviously it must be right.
Also, I must say I did slap my forehead when I saw the parent's solution to the same problem that avoids the conditional by just calling drop. Hopefully I will remember this in the future.
Reply
That interests me...
The theorist in me wants to say "If there's a false assumption in your code, then it's wrong. The bug may not have manifested yet, but Murphey says it will if you ignore it, so you'd best fix it now whether that's the bug you thought you were working on or not."
Having said that, the engineer in me is more like "Oh man, that's gonna open up a huge can of worms: If I fix it so that the assumption holds, then something else will turn out to rely on the thing I changed, and if I try to remove the assumption from the code, then I'll probably have to follow through every dependency from this point out... And I'll have to look see if this assumption is made elsewhere... Maybe it'd be best to just fix the bug I was working on, and see if the code works ok for the cases I'm interested in?"
I'm not sure yet what I think about the relationship between these two guys in my head (though now I look at what I just wrote, I think it's interesting that the theorist in me talked about someone else's code, while the engineer in me talked about his own code ^_^ ).
I think the latter solution would be a lot easier to do if there was an array of tests on hand, defining the cases I'm interested in. Having said that, I think you might well be able to do a similar trick with theory - if you can see what effects the failed assertion will have on the output - you just change the specification to match what you can actually do ;) I guess I kinda did that when I noted that in my implementation split _ [] = [[]] and I didn't care...
Does haskell help reduce the pain of the engineer, and encourage coding in the style of the theorist? I wonder what working haskellers out there do in real-life situations.
Reply
Leave a comment