Haskell - What does the input of a higher-order function look like if it takes functions as arguments?

Question

I'm working with Haskell, and trying to implement a higher-order function, but I'm having trouble understanding and testing the function because I'm unsure what an input would look like.

Since the function itself is part of a graded assignment, I can't ask for help regarding writing/implementing the function itself, so I've changed the function names and custom type names, so I can use the function as an example on what the input arguments would look like, if you were to type them into the console.

search :: ([(Int,Int)] -> [[(Int,Int)]]) -> ([(Int,Int)] -> Bool) -> [[(Int,Int)]] -> Maybe [(Int,Int)]
search function1 function2 listOfIntegerPairs

function1 takes a list of integer pairs as input and outputs a list of lists containing pairs of integers.

function2 takes a list of integer pairs and outputs a boolean.

I'm unsure as to how one might input the arguments for this higher-order function into the console.

i.e. Would it be something like this where we include the function and it's parameters as arguments?

search (function1([(0,0),(0,1)])) (function2([(0,0),(0,1)])) [(0,0),(0,1)]

This form produces errors, but I can't figure out what the input arguments would look like, and having trouble locating any articles/tutorials which illustrates it. Hence I can't test the function until I work out what the input function arguments look like types out.

Can anyone offer me some guidance? Is what I'm asking even possible?

Answer 1

The find function in Data.List has a similar type.

find :: (a -> Bool) -> [a] -> Maybe a

Without revealing finds definition, we can try using it in ghci. First we'll need to import Data.List since that's where it's defined.

> import Data.List

Pass a declared function

The first argument to find says it needs a function with the type a -> Bool. To pass an argument to find we pass it the whole function. We don't need to call that function first, or give that function arguments, we can treat the function as an ordinary value and pass the entire function to find. This ability to treat functions as ordinary values is what is meant when we talk about "functions as first-class citizens" of the language; we can do anything with functions that we could do with all other types. To pass something to find, we'll need to define it first.

> let divisibleBy3 x = x `mod` 3 == 0

Now, we'll pass the entire divisibleBy3 function to find as its first argument. As the second argument, we'll pass a list that has something we want to find, [4, 7, 9, 10]

> find divisibleBy3 [4, 7, 9, 10]
Just 9

Pass a lambda

Haskell provides other ways to define a function that simply referencing one that has already been defined. A lambda constructs a new anonymous function. If the constructed function has the correct type, we can pass it as the first argument to find.

> find (\x -> x*3 == x + 8) [1,2,3,4,5,6,7,8,9,10]
Just 4

Pass a result

Function types can appear both as arguments to a function and as the result of a function. This means we can make functions that make new functions. We could have written the function composition operator, ., as an ordinary function declaration. To do so, we first need to hide the definition from the prelude.

> import Prelude hiding ((.))
> let f . g = \x -> f (g (x))

Writing it with a lambda on the right-hand side emphasizes that, when applied to only two arguments, function composition returns a function. Anywhere we need a function, we can pass any expression that has the correct type. This means we can pass the result of . into find. It also means we can pass functions defined any of these ways in as the arguments to ..

> find (not . odd) [1, 1, 2, 3, 5, 8]
Just 2

> find (not . divisibleBy3 . (\x -> x*(x+1))) [2, 3, 4, 5, 6]
Just 4

Pass a partial application

When we define a function like

same :: Int -> Int -> Bool
same x y = x - y == 0

The function type constructor -> in the type of same is right associative, which means things on the right are grouped together before things on the left.

same :: Int -> (Int -> Bool)

With these parentheses added we can see that same, which looks like a function of two arguments, can be treated as a function with only one argument, Int, that returns a function, Int -> Bool. We can use a partially applied function to produce functions to pass as arguments.

> let same x y = x - y == 0
> find (same 7) [1..10]
Just 7