Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there a relationship between dollar sign ($) and id function in Haskell?

Tags:

haskell

One of these days I was reading comments on the Monad Challenge (which I highly recommend to any beginner in Haskell, like myself), and I ended up on this thread where I read that ($) = id.

I don't know about scaring people, but many programming languages have concepts that are best demonstrated with small examples that make people say "whoa".

For example, it's amazing that append() in Prolog can be run "backwards" from the concatenated result to yield all the lists that can be concatenated to produce it. Or that the monadic bind operator in Haskell (>>=) can be defined in terms of join and fmap, or that ($) = id.

($) = id !?

< tries it out in Raskell/Ghci >

I see now why it's true, but still... Whoah!! Thanks for that! (...)

I then checked the base-4.10.0.0 code, looking for the definitions of ($) and id, but right at the top I read this:

NOTA BENE: Do NOT use ($) anywhere in this module! The type of ($) is
slightly magical (it can return unlifted types), and it is wired in.
But, it is also *defined* in this module, with a non-magical type.
GHC gets terribly confused (and *hangs*) if you try to use ($) in this
module, because it has different types in different scenarios.

This is not a problem in general, because the type ($), being wired in, is not
written out to the interface file, so importing files don't get confused.
The problem is only if ($) is used here. So don't!

And their implementations are:

-- | Identity function.
id                      :: a -> a
id x                    =  x

-- | Application operator.
{-# INLINE ($) #-}
($)                     :: (a -> b) -> a -> b
f $ x                   =  f x

I tried swapping one by the other on GHCi and all I got was type errors (as I expected). Now, I have more questions than what I started with:

  1. What do they mean by saying that ($) = id?
  2. In which cases is that statement true? Does that mean I can use one instead of the other?
  3. In the base, what is meant by saying that ($) is "slightly magical (it can return unlifted types)" and "being wired in"?
  4. And what about "different types in different scenarios"? I thought that since Haskell is a strongly typed language, once you define a type signature, that signature is retained until the end of Time. Is that not true? Are there cases where one can change a function's type?
like image 290
luispauloml Avatar asked Nov 15 '17 21:11

luispauloml


People also ask

What does dollar sign do in Haskell?

Dollar sign. Since complex statements like a + b are pretty common and Haskellers don't really like parentheses, the dollar sign is used to avoid parentheses: f $ a + b is equivalent to the Haskell code f (a + b) and translates into f(a + b).

What does id mean in Haskell?

id is just the identity function.

What does dollar operator do?

The $ operator is for avoiding parentheses. Anything appearing after it will take precedence over anything that comes before. The primary purpose of the . operator is not to avoid parentheses, but to chain functions.

What does <$> mean in Haskell?

It's merely an infix synonym for fmap , so you can write e.g. Prelude> (*2) <$> [1.. 3] [2,4,6] Prelude> show <$> Just 11 Just "11" Like most infix functions, it is not built-in syntax, just a function definition. But functors are such a fundamental tool that <$> is found pretty much everywhere.


Video Answer


2 Answers

Haskell indeed is strongly typed; the issue is related to some hackery specific to the ($) operator. Unfortunatelly, I have no idea what is it about: hopefully someone will answer your question 3 (and question 4 automatically).

Concerning question 1, look at the types:

id :: a -> a
($) :: (a -> b) -> (a -> b)

Rename c = a -> b and you get ($) :: c -> c, which means that the type of ($) is a specification of the type of id, so that at least types allow us to use id to implement ($).

Now, look at the definition of ($):

f $ x = f x

Let's rewrite it a bit:

($) f = \x -> f x

And apply eta-reduction:

($) f = f

Now it is clearly seen that ($) is just id with a bit more specific type (so that f is always a function).

Note that it doesn't work another way round, since the type of ($) is more restrictive. For example, you can call id 5 and get 5 as a result, but ($) 5 won't typecheck: 5 doesn't have type of the form a -> b.

The point of ($) is that it has very low priority and allows to avoid braces around the arguments of f, and can be used like

someFunction $ whatever complex computation you dont need braces around
like image 106
lisyarus Avatar answered Sep 28 '22 05:09

lisyarus


  1. What do they mean by saying that ($) = id?

The function ($) could be defined as

($) f x = f x

i.e. taking a function and an argument and returning the result of the application. Equivalently, thanks to currying, we can interpret that as taking only f and returning a function of x.

($) f = \x -> f x

Here, we can note that the function \x -> f x maps any input x to f x -- that's also what f does! So, we can simplify the definition to

($) f = f

Now, this is the same as the identity function definition id y = y, so we might as well write

($) = id
  1. In which cases is that statement true? Does that mean I can use one instead of the other?

The equation holds always, but there are two caveats.

The first one is that ($) has a more restricted type than the one of id, since ($) f = f holds only for a function f, not for any value f. This means that you can replace ($) with id, but not vice versa. When writing

($) = id

one could make the implicit type argument explicit and write that, for any types a and b

($) @ a @ b = id @ (a->b)

The other caveat is that, in the presence of higher-ranked function, ($) receives some special handling during type checking, while id does not. This is point 3 blow.

  1. In the base, what is meant by saying that ($) is "slightly magical (it can return unlifted types)" and "being wired in"?

Normally, in polymorphic functions such as

id :: forall a . a -> a

the type variable a can be instantiated to other types, but only under some restrictions. For instance, a can be instantiated to Int, but can not be instantiated to another polymorphic type forall b . .... This keeps the type system predicative, which helps greatly during type inference.

Usually, this is not an issue in everyday programming. However, some functions use rank-2 types, e.g. runST

runST :: (forall s. ST s x) -> x

If we write

runST (some polymorphic value here)

the type system can type check that. But if we use the common idiom

runST $ some polymorphic value here

then the type inference engine has to take the type of ($)

($) :: forall a b . (a -> b) -> a -> b

and choose a ~ forall s. ST s x which is polymorphic, hence forbidden.

Since this idiom is too common, the GHC developers decided to add a special case to the typing of ($) to allow this. Since this is a bit ad-hoc, if you define your own ($) (possibly under another name), and try to type check runST $ ... this will fail since it does not use the special case.

Further, a can not be instantiated to unboxed types such as Int#, or unboxed tuples (# Int#, Int# #). These are GHC extensions which allow writing functions which pass a "raw" integer, without the usual thunk wrapper. This can change the semantics, e.g. making functions stricter than they are. Unless you want to squeeze more performance from some numeric code, you can ignore these.


(I'm leaving this part here, but lisyarus already covered it more precisely.)

f $ x = f x
-- i.e.
($) f x = f x
-- i.e.
($) f x = id f x
-- eta contraction
($) f = id f
-- eta contraction
($) = id

Basically, ($) is id, but with a more restrictive type. id can be used on arguments of any type, ($) instead takes a function argument.

($) :: (a -> b) -> a -> b
-- is better read as
($) :: (a -> b) -> (a -> b)
-- which is of the form (c -> c) with c = (a -> b)

Note that id :: c -> c, so the type of ($) is indeed a special case.

And what about "different types in different scenarios"? I thought that since Haskell is a strongly typed language, once you define a type signature, that signature is retained until the end of Time. Is that not true? Are there cases where one can change a function's type?

In the code of the libraries which define ($), GHC has to play some tricks to get the special typing rules to work for the other libraries and programs. For that, apparently it is required not to use ($) in said library. Unless you are developing GHC or the base module which happens to define ($), you can ignore this. It is an implementation detail internal to the compiler, not something that the user of the compiler and libraries must know.

like image 24
chi Avatar answered Sep 28 '22 03:09

chi