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?

It'd be best to leave the type signature the same as your problem The type a -> [a] is not that of a function that "takes a list of integer pairs as inputs and outputs a list of lists containing pairs of integers", it's that of a function that takes a value and returns a list of values. This can be specialized to what you intend it to be, but you could also pass it e.g. a Bool. Also, the point of higher order functions is to pass another function as an argument, not the result of another function, that's regular order functions. Try search function1 function1 [(0,0),(0,1)]. — bheklilr
The easiest thing might be to define the functions explicitly: myFunction1 :: bool -> [bool] myFunction1 b = [true, false, b] or whatever you want your myFunction1 to be. Then you can pass myFunction1 as the argument. — lmm
Quite literally, the search function is called in the same manner it's declared. Think of the map function: map length ["this", "is", "a", "test"] would return [4,2,1,4], it isn't called as map (length ["this", "is", "a", "test"]) ["this", "is", "a", "test"], which wouldn't be the same anyway, since it would reduce to something like map 4 ["this", "is", "a", "test"], since that argument list has length 4, and mapping the "function 4" is nonsensical. — bheklilr
Oops, I should say the functions function1, function2 are defined explicitly elsewhere in the document, and I'm not allowed to change the type declaration used by the fuctions. The thing that confuses me is where does function1 and function2 get its parameters? Will they take listOfIntegerPairs as their own argument? i.e. search function1 function2 [(0,0),(1,0)]? — Wolff
@Wolff I'm not saying that you should change the type declarations, just that you should edit your question so that the search function has the same type signature. Haskell type signatures are very informative and useful, intentionally providing the wrong type signature when asking for help would be like asking for help finding a bug in a C++ function, but removing the lines that cause the bug in the question. — bheklilr

Cirdec Cirdec · Accepted Answer · 2015-02-17T15:45:32

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