7

I am a Haskell novice. I am trying to create a mini-language within Haskell, and would like if possible to have a higher-order function called opp (short for "opposite") that converts a number of familiar functions into their obvious opposites. For example, opp succ would be the function pred, opp head would be last, and so on. I don't have some general definition of what it means to convert a function into its opposite: I just want to pick a few key examples and declare what their opposites. So I want a highly polymorphic function that is hardly ever defined.

The difficulty seems to be that I want to recognise the functions by their names rather than by their essences (so to speak). One manifestation of that difficulty is that if I write

opp succ = pred

then Haskell treats succ as a variable and therefore gives me a constant function that always takes the value pred. What I really want is to say something more like, "If you ever see the string opp succ then think of it as another name for pred." But after searching around for quite a while, I can't find out how to do that (if it's possible at all).

To summarize, I would like to define a function

opp :: (a -> b) -> (a -> b)

by saying things like

opp succ = pred

opp pred = succ

opp head = last

opp last = head

and adding to this list whenever I feel like it. Obviously I can't do it like that, but is there some non-horrible way of achieving the same effect?

user15553
  • 301
  • 1
  • 6
  • Allright. But this notion of "opposite" seems rather vaguely specified indeed then. – leftaroundabout Jun 16 '14 at 10:24
  • That's sort of the point. Because there isn't a nice definition of "opposite", I want to define it on a case-by-case basis. – user15553 Jun 16 '14 at 10:28
  • 1
    @user15553 why have "opposite" at all then? At this point you can have `oppPred = succ` and you don't lose power of expression relative to what you specified in the question. – András Kovács Jun 16 '14 at 10:31
  • It's because in the mini-language it is important to be able to think of `opp` itself as an abstract concept, so that in some sense the relationship between `succ` and `pred` is "the same" as the relationship between `head` and `last`. One (not the only) advantage of this would be so that I can use it to construct other functions such as `oppPair f = (f, opp f)` rather than having to construct lots of similar functions in essentially the same way. – user15553 Jun 16 '14 at 10:58

3 Answers3

11

Yes you can, however you require RankNTypes in order to have a nice implementation.

{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE RankNTypes #-}
module Opposites where

class Opposite f where
  makeOpposite :: (a -> b) -> (a -> b) -> f a b


data FunctionAndOpposite a b = FunctionAndOpposite (a -> b) (a -> b)

instance Opposite (->) where
  makeOpposite = const

instance Opposite FunctionAndOpposite where
  makeOpposite = FunctionAndOpposite

opp :: FunctionAndOpposite a b -> a -> b
opp (FunctionAndOpposite _ f) = f

type a :<-> b = forall f. Opposite f => f a b

succ' :: Enum a => a :<-> a
succ' = makeOpposite succ pred

pred' :: Enum a => a :<-> a
pred' = makeOpposite pred succ

head' :: [a] :<-> a
head' = makeOpposite head last

last' :: [a] :<-> a
last' = makeOpposite last head

Example usage:

> head' [1,2,3]
1
> opp head' [1,2,3]
3

How it works

Firstly, there is the Opposite class. This just describes an f a b that can be constructed out of two functions of (a -> b) (the normal and opposite functions).

Next, a data type FunctionAndOpposite is defined. This just stores the two functions. Now both the standard function, and this are made instances of the class Opposite. The function instance just discards the opposite function.

Now the opp function can be defined. This just takes the second function out of a FunctionAndOpposite.

Finally we get the line that brings it all together: 

type a :<-> b = forall f. Opposite f => f a b

what this defines is a type synonym which takes two input types a and b, then returns a type f a b, where f can be any Opposite (depending on what is needed).

(the :<-> is just a fancy name for the type enabled with TypeOperators).

Consider the code head' [1,2,3]. head' has the type forall f. Opposite f => f [a] a. However, as it is being used as a function application (since it has an argument straight afterwards), f must be ->. Therefore, the function implementation of Opposite is used, returning the first argument to makeOpposite, which is head (great!).

However, lets say opp head' [1,2,3] is called. opp has the type FunctionAndOpposite a b -> a -> b, so f must be FunctionAndOpposite. Therefore, the FunctionAndOpposite instance of Opposite is called, creating the data type using both arguments to makeOpposite. opp then pulls out the second function, which is last.

As an aside, this is done using a similar technique used in the lens library for Isomorphism. An isomorphism is basically a pair of functions that are inverses of each other. Eg (+2) and (-2), reverse and itself. This is probably a more useful concept in general, as it allows you to run operations on a data type over a transformation. See Control.Lens.Iso for more details, however note that to understand this you would need to understand the lens concepts, which is a pretty big job.

David Miani
  • 14,518
  • 2
  • 47
  • 66
  • 1
    This looks great -- and at the kind of elementary level that I can hope to understand when I've made an effort to digest it. Thank you very much. – user15553 Jun 16 '14 at 12:56
2

If we reformulate your question into this form the problem may become more clear to you:

opp x | x == succ = pred
      | x == pred = succ

This will give you the error that (a -> b) has no Eq instance, which it cannot have since equality for functions is undefined.

A solution to this would be to define a separate datatype that you can pattern match on.

nulvinge
  • 1,600
  • 8
  • 17
0

It might be possible to use some kind of hash map based on the closures adress on heap to identify the functions. Then you could create such a inverse table. Unfortunately, you would not really get what you want, since functions are just values and as such they are created whenever the compiler (or runtime) decides to do so.

E.g. even when you say that 

opp head = last

You might (depending on the compiler implementation) achieve nothing for

opp (λx.head x)

In fact, you do not have a reliable identity on function values - hence I think there is no usable way to do what you intend to do.

choeger
  • 3,562
  • 20
  • 33