CODEWITHSUNDEEP
haskell
xcoder
xcoder

Reputation: 1436

Pattern match Haskell Higher order function?

Imagine I have a custom type and two functions:

type MyType = Int -> Bool

f1 :: MyType -> Int
f3 :: MyType -> MyType -> MyType

I tried to pattern match as follows:

f1 (f3 a b i) = 1

But it failed with error: Parse error in pattern: f1. What is the proper way to do the above?? Basically, I want to know how many f3 is there (as a and b maybe f3 or some other functions).

Upvotes: 3

Views: 876

Answers (2)

J. Abrahamson
J. Abrahamson

Reputation: 74334

Once a function has been applied its syntactic form is lost. There is now way, should I provide you 2 + 3 to distinguish what you get from just 5. It could have arisen from 2 + 3, or 3 + 2, or the mere constant 5.

If you need to capture syntactic structure then you need to work with syntactic structure.

data Exp = I Int | Plus Exp Exp

justFive :: Exp
justFive = I 5

twoPlusThree :: Exp
twoPlusThree = I 2 `Plus` I 3

threePlusTwo :: Exp
threePlusTwo = I 2 `Plus` I 3

Here the data type Exp captures numeric expressions and we can pattern match upon them:

isTwoPlusThree :: Exp -> Bool
isTwoPlusThree (Plus (I 2) (I 3)) = True
isTwoPlusThree _ = False

But wait, why am I distinguishing between "constructors" which I can pattern match on and.... "other syntax" which I cannot?

Essentially, constructors are inert. The behavior of Plus x y is... to do nothing at all, to merely remain as a box with two slots called "Plus _ _" and plug the two slots with the values represented by x and y.

On the other hand, function application is the furthest thing from inert! When you apply an expression to a function that function (\x -> ...) replaces the xes within its body with the applied value. This dynamic reduction behavior means that there is no way to get a hold of "function applications". They vanish into thing air as soon as you look at them.

Upvotes: 4

Ben
Ben

Reputation: 71400

You can't pattern match on a function. For (almost) any given function, there are an infinite number of ways to define the same function. And it turns out to be mathematically impossible for a computer to always be able to say whether a given definition expresses the same function as another definition. This also means that Haskell would be unable to reliably tell whether a function matches a pattern; so the language simply doesn't allow it.

A pattern must be either a single variable or a constructor applied to some other patterns. Remembering that constructor start with upper case letters and variables start with lower case letters, your pattern f3 a n i is invalid; the "head" of the pattern f3 is a variable, but it's also applied to a, n, and i. That's the error message you're getting.

Since functions don't have constructors, it follows that the only pattern that can match a function is a single variable; that matches all functions (of the right type to be passed to the pattern, anyway). That's how Haskell enforces the "no pattern matching against functions" rule. Basically, in a higher order function there's no way to tell anything at all about the function you've been given except to apply it to something and see what it does.

The function f1 has type MyType -> Int. This is equivalent to (Int -> Bool) -> Int. So it takes a single function argument of type Int -> Bool. I would expect an equation for f1 to look like:

f1 f = ...

You don't need to "check" whether it's an Int -> Bool function by pattern matching; the type guarantees that it will be.

You can't tell which one it is; but that's generally the whole point of taking a function as an argument (so that the caller can pick any function they like knowing that you'll use them all the same way).

I'm not sure what you mean by "I want to know how many f3 is there". f1 always receives a single function, and f3 is not a function of the right type to be passed to f1 at all (it's a MyType -> MyType -> MyType, not a MyType).

Upvotes: 7

Related Questions