CODEWITHSUNDEEP
haskell
Sindu_
Sindu_

Reputation: 1455

Higher Order Function in Haskell

I have written the following code. I know that a higher order function is a function that takes in another function and returns a function as a result. But I can't clearly distinguish a function if it is higher order or not. Is sort a higher order function? How do I find out if a function is higher order or not?

sortString :: String -> [String]
sortString x = sort (convertStringIntoList x)

Upvotes: 1

Views: 1863

Answers (2)

Greg Bacon
Greg Bacon

Reputation: 139411

A higher-order function is a function that takes another function as an argument, produces another function as a result, or perhaps both.

The function in your question has a single argument that is a string, not a function. When applied, your function’s value is an array of strings, not a function. Therefore, it is an ordinary function.

A similar function that is higher order is

sortString :: (Char -> Char -> Ordering) -> String -> [String]
sortString cmp s = map (:[]) $ sortBy cmp s

The power of higher-order functions is the flexibility they provide. Providing different functions produces different results:

ghci> sortString compare "slkdjfs"
["d","f","j","k","l","s","s"]

ghci> sortString (flip compare) "slkdjfs"
["s","s","l","k","j","f","d"]

In case you aren’t familiar, compare provides an Ordering relative to its arguments, e.g.,

ghci> compare 'a' 'b'
LT
ghci> compare 'b' 'a'
GT

As you may have noticed, flip is itself another higher-order function that reorders or flips the arguments to another function. Using flip as in the code above allows us to sort the list in descending rather than ascending order.

Upvotes: 6

Bridget
Bridget

Reputation: 175

If sort takes the inputs convertStringIntoList and x, then it is higher order. If x is first acted on by convertStringIntoList, then by sort, then sort is not a higher order function (the functions are just nested).

Based on the input and output types of sort (http://zvon.org/other/haskell/Outputlist/sort_f.html) I'd say it's the first. (Also, based on the way it's formatted, this has to be the case.) The type definition Ord a => [a] -> [a] means that the function takes a list of "a" and returns a list of "a", where a is a type of the class "Ord". Basically this just means it could be a Char, Double, Float, Int or Integer (http://zvon.org/other/haskell/Outputprelude/Ord_c.html). So the input cannot be a function.

In general you can find out if a function is higher order by looking up what its input and output types are. If either of these can be functions, then the function can be a higher order function.

You potentially have a bit of a grey area if the input may or may not be a function. For example, say you had a function that took an input and just returned that same output (pointless, but it's just an example). Then I would say that if you used a character as an input, it wouldn't be acting as a higher order function, but if you used a function as an input, then it would. Not sure about that part though, just my gut feeling.

Upvotes: 2

Related Questions