"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 think is probably a fairly static typey style.
This is not a beginners haskell tutorial - I'm going to assume that you know about lists, higher order functions and fold in particular. This is for people that understand functional programming, but are frustrated by strongly statically typed functional programming. Actually, if there's anyone other than pozorvlak reading this who's in that position, I'd appreciate a comment - I've no idea how many of you exist, or if this is the sort of thing that helps.
The problem is to write a function that works in a similar way to the perl "split" function. The one I choose to write behaves slightly differently from the perl one - I'll work with polymorphic lists rather than just strings of characters (there's no reason not to), and I'll restrict the argument I split on to being a singleton in the list. I appreciate that no true perl programmer would forego this functionality, but I think it makes this little toy far easier to understand, and the function is still useful even with that restriction.
There are lots of ways to write this function, and this is how I happened to hack it together earlier today, when I needed to use use it for something. There are certainly better ways to write the function - my intention here is to try to give voice to as many as possible of the little subconscious thoughts that make programming happen.
This is statically typed programming, so we start with the type we want:
split :: b -> [b] -> [[b]]
It's clearly a list function, and map probably isn't going to do it because ther's no obvious relationship between the length of the output list and the length of the input list. Will fold work?
foldl :: (a -> b -> a) -> a -> [b] -> a
In the case where a is equal to [[b]] we have:
foldl :: ([[b]] -> b -> [[b]]) -> [[b]] -> [b] -> [[b]]
and I'll be able to do:
split x = foldl f y
Which looks like it'll typecheck for some approproate f and y.
Let's choose the simplest thing first - y. This is the bounds case of the fold - the thing that gets returned of the final argument is just an empty list. "" won't type check as [[b]], so let's try [[]], and see what happens. Now, can we find the f? If we can, it will certainly be of type:
f :: [[b]] -> b -> [[b]]
If y is [[]], then f doesn't need to worry about the [] case for the first arg, so we can have (remembering that x is in scope already):
f (acc@(y:ys)) z = if (z==x) then []:acc
else (z:y):ys
Notice that we've used == in there, so we'll need our list elements to be in class Eq. The function as a whole, then, will look like:
split :: (Eq a) => a -> [a] -> [[a]]
split x = foldl f [[]] where
f (acc@(y:ys)) z = if (z==x) then []:acc
else (z:y):ys
Let's try testing it :)
*Main> split ',' "a list, of, wordey thingies "
[" seigniht yedrow ","fo ","tsil a"]
*Main>
lol :)
*Main> reverse $ map reverse $ split ',' "a list, of, wordey thingies "
["a list"," of"," wordey thingies "]
*Main>
That's better.
The behaviour on the empty list case is still slightly annoying:
*Main> reverse $ map reverse $ split ',' ""
[""]
*Main>
...but at this stage I had what I needed for my own little hack, so I was happy. This isn't exercise-code that's being marked - it's not particularly pretty or general or fast. It's just a little snippit of something I wanted to run. If you've been coding in the same paradigm (scripts, OO, whatever) for a long time, then I imagine this thought process will seem like an awful lot of effort, for very little result. I don't think it's a lot of effort though - if I hadn't made the decision to self-analyse while I was writing this little function, I'd have done it in a few seconds without thinking about it. I think that all programmers do a comparable amount of work whenever they write a little function or procedure like this, but it's all subconscious, and we rarely talk or even think about it.
I'd be interested to see how other people solve similarly simple problems. I'm not interested in the solution itself, I'm interested in the thoughts that lead you to that solution. How do the rest of you do it?
This is not a beginners haskell tutorial - I'm going to assume that you know about lists, higher order functions and fold in particular. This is for people that understand functional programming, but are frustrated by strongly statically typed functional programming. Actually, if there's anyone other than pozorvlak reading this who's in that position, I'd appreciate a comment - I've no idea how many of you exist, or if this is the sort of thing that helps.
The problem is to write a function that works in a similar way to the perl "split" function. The one I choose to write behaves slightly differently from the perl one - I'll work with polymorphic lists rather than just strings of characters (there's no reason not to), and I'll restrict the argument I split on to being a singleton in the list. I appreciate that no true perl programmer would forego this functionality, but I think it makes this little toy far easier to understand, and the function is still useful even with that restriction.
There are lots of ways to write this function, and this is how I happened to hack it together earlier today, when I needed to use use it for something. There are certainly better ways to write the function - my intention here is to try to give voice to as many as possible of the little subconscious thoughts that make programming happen.
This is statically typed programming, so we start with the type we want:
split :: b -> [b] -> [[b]]
It's clearly a list function, and map probably isn't going to do it because ther's no obvious relationship between the length of the output list and the length of the input list. Will fold work?
foldl :: (a -> b -> a) -> a -> [b] -> a
In the case where a is equal to [[b]] we have:
foldl :: ([[b]] -> b -> [[b]]) -> [[b]] -> [b] -> [[b]]
and I'll be able to do:
split x = foldl f y
Which looks like it'll typecheck for some approproate f and y.
Let's choose the simplest thing first - y. This is the bounds case of the fold - the thing that gets returned of the final argument is just an empty list. "" won't type check as [[b]], so let's try [[]], and see what happens. Now, can we find the f? If we can, it will certainly be of type:
f :: [[b]] -> b -> [[b]]
If y is [[]], then f doesn't need to worry about the [] case for the first arg, so we can have (remembering that x is in scope already):
f (acc@(y:ys)) z = if (z==x) then []:acc
else (z:y):ys
Notice that we've used == in there, so we'll need our list elements to be in class Eq. The function as a whole, then, will look like:
split :: (Eq a) => a -> [a] -> [[a]]
split x = foldl f [[]] where
f (acc@(y:ys)) z = if (z==x) then []:acc
else (z:y):ys
Let's try testing it :)
*Main> split ',' "a list, of, wordey thingies "
[" seigniht yedrow ","fo ","tsil a"]
*Main>
lol :)
*Main> reverse $ map reverse $ split ',' "a list, of, wordey thingies "
["a list"," of"," wordey thingies "]
*Main>
That's better.
The behaviour on the empty list case is still slightly annoying:
*Main> reverse $ map reverse $ split ',' ""
[""]
*Main>
...but at this stage I had what I needed for my own little hack, so I was happy. This isn't exercise-code that's being marked - it's not particularly pretty or general or fast. It's just a little snippit of something I wanted to run. If you've been coding in the same paradigm (scripts, OO, whatever) for a long time, then I imagine this thought process will seem like an awful lot of effort, for very little result. I don't think it's a lot of effort though - if I hadn't made the decision to self-analyse while I was writing this little function, I'd have done it in a few seconds without thinking about it. I think that all programmers do a comparable amount of work whenever they write a little function or procedure like this, but it's all subconscious, and we rarely talk or even think about it.
I'd be interested to see how other people solve similarly simple problems. I'm not interested in the solution itself, I'm interested in the thoughts that lead you to that solution. How do the rest of you do it?