Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Haskell: Typeclass vs passing a function

To me it seems that you can always pass function arguments rather than using a typeclass. For example rather than defining equality typeclass:

class Eq a where 
  (==)                  :: a -> a -> Bool

And using it in other functions to indicate type argument must be an instance of Eq:

elem                    :: (Eq a) => a -> [a] -> Bool

Can't we just define our elem function without using a typeclass and instead pass a function argument that does the job?

like image 527
Mahdi Avatar asked Apr 16 '20 05:04

Mahdi


People also ask

What is Typeclass in Haskell?

What's a typeclass in Haskell? A typeclass defines a set of methods that is shared across multiple types. For a type to belong to a typeclass, it needs to implement the methods of that typeclass. These implementations are ad-hoc: methods can have different implementations for different types.

What does EQ mean in Haskell?

The Eq class defines equality ( == ) and inequality ( /= ). All the basic datatypes exported by the Prelude are instances of Eq , and Eq may be derived for any datatype whose constituents are also instances of Eq . The Haskell Report defines no laws for Eq .

What is it called when the type of a function contains one or more class constraints?

Overloaded Functions. A polymorphic function is called overloaded if its type contains one or more class constraints.

What are function types in Haskell?

Haskell has first-class functions : functions are values just like integers, lists, etc. They can be passed as arguments, assigned names, etc. … val is value of type Int , and half_of is a value of type Float -> Float .


2 Answers

Yes. This is called "dictionary passing style". Sometimes when I am doing some especially tricky things, I need to scrap a typeclass and turn it into a dictionary, because dictionary passing is more powerful1, yet often quite cumbersome, making conceptually simple code look quite complicated. I use dictionary passing style sometimes in languages that aren't Haskell to simulate typeclasses (but have learned that that is usually not as great an idea as it sounds).

Of course, whenever there is a difference in expressive power, there is a trade-off. While you can use a given API in more ways if it is written using DPS, the API gets more information if you can't. One way this shows up in practice is in Data.Set, which relies on the fact that there is only one Ord dictionary per type. The Set stores its elements sorted according to Ord, and if you build a set with one dictionary, and then inserted an element using a different one, as would be possible with DPS, you could break Set's invariant and cause it to crash. This uniqueness problem can be mitigated using a phantom existential type to mark the dictionary, but, again, at the cost of quite a bit of annoying complexity in the API. This also shows up in pretty much the same way in the Typeable API.

The uniqueness bit doesn't come up very often. What typeclasses are great at is writing code for you. For example,

catProcs :: (i -> Maybe String) -> (i -> Maybe String) -> (i -> Maybe String)
catProcs f g = f <> g

which takes two "processors" which take an input and might give an output, and concatenates them, flattening away Nothing, would have to be written in DPS something like this:

catProcs f g = (<>) (funcSemi (maybeSemi listSemi)) f g

We essentially had to spell out the type we're using it at again, even though we already spelled it out in the type signature, and even that was redundant because the compiler already knows all the types. Because there's only one way to construct a given Semigroup at a type, the compiler can do it for you. This has a "compound interest" type effect when you start defining a lot of parametric instances and using the structure of your types to compute for you, as in the Data.Functor.* combinators, and this is used to great effect with deriving via where you can essentially get all the "standard" algebraic structure of your type written for you.

And don't even get me started on MPTC's and fundeps, which feed information back into typechecking and inference. I have never tried converting such a thing to DPS -- I suspect it would involve passing around a lot of type equality proofs -- but in any case I'm sure it would be a lot more work for my brain than I would be comfortable with.

--

1Unless you use reflection in which case they become equivalent in power -- but reflection can also be cumbersome to use.

like image 96
luqui Avatar answered Sep 18 '22 18:09

luqui


Yes. That (called dictionary passing) is basically what the compiler does to typeclasses anyway. For that function, done literally, it would look a bit like this:

elemBy :: (a -> a -> Bool) -> a -> [a] -> Bool
elemBy _ _ [] = False
elemBy eq x (y:ys) = eq x y || elemBy eq x ys

Calling elemBy (==) x xs is now equivalent to elem x xs. And in this specific case, you can go a step further: eq has the same first argument every time, so you can make it the caller's responsibility to apply that, and end up with this:

elemBy2 :: (a -> Bool) -> [a] -> Bool
elemBy2 _ [] = False
elemBy2 eqx (y:ys) = eqx y || elemBy2 eqx ys

Calling elemBy2 (x ==) xs is now equivalent to elem x xs.

...Oh wait. That's just any. (And in fact, in the standard library, elem = any . (==).)

like image 24
Joseph Sible-Reinstate Monica Avatar answered Sep 18 '22 18:09

Joseph Sible-Reinstate Monica