More playing with sections (and flip) in haskell

Last week I wrote about sections in Haskell, and discovered flip. Today I hit upon a problem which got me thinking about them again, leading to one of those wonderful moments when Stuff You Just Learnt turns out to be exactly what you need to solve the problem you’ve got right now. (Then you blog about it and find an Even Better Way, as it turns out.)

I’ve been writing some file-manipulation code, and along the way had written the following function:

-- | Check if a given string (subject) ends with another (target).
endswith :: String -> String -> Bool
endswith sub tgt = drop (length sub - length tgt) sub == tgt

(Actually I’ve forgotten now whether I wrote this myself or found it somewhere, but it’s clearly not a new problem. If anyone knows a source for the above code, please do tell so I can attribute it. Anyway…)

So then you can do:

*Ew> endswith "banana" "na"
True
*Ew> endswith "banana" "moo"
False

So far so good. Later, I had a list of filenames, and I wanted to filter it down to just those ending with a particular suffix. Initially, unthinkingly, I tried:

*Ew> filter (endswith "na") ["banana", "cat", "iguana", "mastodon"]
[]

Spot the cunning use of a section. Actually not so cunning, as it turns out – the empty list is not the result I was hoping for! The problem is that the first parameter of endswith is the subject (the string to be searched) not the target (the string to be searched for) so the section (endswith "na") is not the function which checks if a string ends with “na”. It’s the function which, given a string, checks if “na” ends in that string:

*Ew> (endswith "na") "banana"
False
*Ew> (endswith "na") "a"
True
*Ew> (endswith "na") "na"
True

My first reaction was to just swap the parameters around. Let’s call this version endswith'. It’s exactly the same as endswith except for the parameter order:

endswith' :: String -> String -> Bool
endswith' tgt sub = drop (length sub - length tgt) sub == tgt

Then (endswith' "na") is the section I’m looking for, and in particular works as I want under filter:

*Ew> (endswith' "na") "banana"
True
*Ew> filter (endswith' "na") ["banana", "cat", "iguana", "mastodon"]
["banana","iguana"]

I only use endswith in a couple of places, so this change was totally viable. Lesson learnt (or so I thought): you have to think carefully about parameter order when writing functions, because some sections will be more useful than others. Obviously with endswith, the section with bound target is more generally useful than the section with bound subject.

Later, I realised this lesson is bogus, or at least not very strong. I mean, there’s probably something in it, but I didn’t actually have to swap the parameters to make my filter work. That’s exactly what flip does:

*Ew> ((flip endswith) "na") "banana"
True
*Ew> filter ((flip endswith) "na") ["banana", "cat", "iguana", "mastodon"]
["banana","iguana"]

What’s going on here? (flip endswith) is endswith with the parameters flipped. Thus ((flip endswith) "na") is exactly the same function as (endswith' "na") which, as we saw above, does what I want. So in the end, I didn’t have to replace endswith with endswith' to get my filter to work – I could just flip it. Bearing in mind I didn’t even know flip existed a week ago, I felt pretty smug to realise this. :-)

The next question on my mind is what you might call “generalised sections for multi-parameter functions”… If I have a 4-parameter function and I want to build a section where 2 of the parameters are bound (say), and it’s not the first two, how do I do it? Stupid toy example:

f :: Int -> Int -> Int -> Int -> Int
f a b c d = a + b + c + d

Can I make a section representing f with b fixed at 3, and d fixed at 5, say? I know I can do this:

g :: Int -> Int -> Int
g a c = f a 3 c d

but can we do it inline, as it were, as with the section approach? Answers on a postcard to the comments page, please! :-) I suspect currying‘s going to wind up in there somewhere…

Postscript

That’s all I originally intended to blog about; when chasing links to support this post, however, I read this and learnt two more interesting things.

First, someone has, of course, solved this problem already, and I can just use isSuffixOf to get this job done (Strings in haskell are Lists of Chars). So now I get to throw endswith away – w00t, less code. A fundamental lesson: once the language starts making sense, learn what’s in the standard libraries!

Second, thanks to Haskell’s ability to deal with functions in infix form, the section (isSuffixOf "na") can also be written as ("na" `isSuffixOf`) which is, I suppose, more natural (provided you’re not scared off by the backticks, which I’m trying not to be). Then we have:

*Ew> filter ("na" `isSuffixOf`) ["banana", "cat", "iguana", "mastodon"]
["banana","iguana"]

Sweet.

2 Responses to “More playing with sections (and flip) in haskell”

  1. Jamie
    April 27th, 2007 | 3:10 pm

    Use an anonymous function.

    eg

    map (\ (a,c) -> f a 3 c d) [(1,2),(5,6)]

    =

    [(f 1 3 2 d) , (f 5 3 6 d)]

  2. May 8th, 2007 | 11:40 am

    Just a small nitpick: I think the term “section” refers only to the syntactic sugar for infix functions. “Partial application” is the more general term.

    Also, remember that function application associates to the left. So

    ((flip endswith) "na") "banana"

    can be simplified to

    flip endswith "na" "banana"