1

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)
5
  • Higher order functions can either take functions as arguments, or return functions (or both). Your function just takes a String and returns a list of String, so it's not higher order. However, if your sort function also took a function (like a comparison operator to determine ordering), then it would be higher-order. Commented Feb 8, 2012 at 4:15
  • In Haskell, all functions with at least two arguments return another function: a -> b -> c is the same as a -> (b -> c). This means defining higher-order functions as returning a function is too broad--it would even include things like (+)! Commented Feb 8, 2012 at 4:28
  • Yeah, but that's the definition of higher-order. Haskell pretty much lives and breathes higher order functions. Commented Feb 8, 2012 at 4:31
  • Looking at Wikipedia, there are different definitions of a "higher-order function". Particularly, the one for typed lambda calculus defines them as any function in the form (τ₁ → τ₂) → τ₃, and is probably the most applicable one for Haskell. Commented Feb 8, 2012 at 4:34
  • When I need to add 1 to everything in a list, I use (+1) -- I am using (+) to return a procedure, so (+) is (or at least can be) a higher order procedure. In Haskell, I think that in many cases, higher-orderness probably needs to be decided on a case by case basis. Commented Feb 8, 2012 at 4:37

2 Answers 2

6

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.

Sign up to request clarification or add additional context in comments.

3 Comments

Is it possible to make sortString a higher order function and get the following input and output Input:"telephone table carrying books" Output: ["books","carrying","table","telephone"]
@Sindu_ If that's input and output of sortString, it's not a higher order function. None of its input or outputs are functions. There's no need "to make it a higher order function" for it to do that.
@Sindu_ Take a look at Haskell's words function.
2

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.

1 Comment

Also, sortString definitely isn't a higher order function, since neither the input or the output are functions.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.