[ACCEPTED]-How do you do generic programming in Haskell?-generic-programming

Accepted answer
Score: 31

This is closely related to your other question 53 about Haskell and quicksort. I think you 52 probably need to read at least the introduction of a 51 book about Haskell. It sounds as if you 50 haven't yet grasped the key point about 49 it which is that it bans you from modifying 48 the values of existing variables.

Swap (as 47 understood and used in C++) is, by its very 46 nature, all about modifying existing values. It's 45 so we can use a name to refer to a container, and 44 replace that container with completely different 43 contents, and specialize that operation 42 to be fast (and exception-free) for specific 41 containers, allowing us to implement a modify-and-publish 40 approach (crucial for writing exception-safe 39 code or attempting to write lock-free code).

You 38 can write a generic swap in Haskell, but 37 it would probably take a pair of values 36 and return a new pair containing the same 35 values with their positions reversed, or 34 something like that. Not really the same 33 thing, and not having the same uses. It 32 wouldn't make any sense to try and specialise 31 it for a map by digging inside that map 30 and swapping its individual member variables, because 29 you're just not allowed to do things like 28 that in Haskell (you can do the specialization, but 27 not the modifying of variables).

Suppose 26 we wanted to "measure" a list in Haskell:

measure :: [a] -> Integer

That's 25 a type declaration. It means that the function 24 measure takes a list of anything (a is a generic 23 type parameter because it starts with a 22 lowercase letter) and returns an Integer. So 21 this works for a list of any element type 20 - it's what would be called a function template 19 in C++, or a polymorphic function in Haskell 18 (not the same as a polymorphic class in 17 C++).

We can now define that by providing 16 specializations for each interesting case:

measure [] = 0

i.e. measure 15 the empty list and you get zero.

Here's a 14 very general definition that covers all 13 other cases:

measure (h:r) = 1 + measure r

The bit in parentheses on the 12 LHS is a pattern. It means: take a list, break 11 off the head and call it h, call the remaining 10 part r. Those names are then parameters 9 we can use. This will match any list with 8 at least one item on it.

If you've tried 7 template metaprogramming in C++ this will 6 all be old hat to you, because it involves 5 exactly the same style - recursion to do 4 loops, specialization to make the recursion 3 terminate. Except that in Haskell it works 2 at runtime (specialization of the function 1 for particular values or patterns of values).

Score: 9

As Earwicker sais, the example is not as 4 meaningful in Haskell. If you absolutely 3 want to have it anyway, here is something 2 similar (swapping the two parts of a pair), c&p 1 from an interactive session:

GHCi, version 6.8.2: http://www.haskell.org/ghc/  :? for help
Loading package base ... linking ... done.
Prelude> let swap (a,b) = (b,a)
Prelude> swap("hello", "world")
Prelude> swap(1,2)
Prelude> swap("hello",2)
Score: 6

In Haskell, functions are as generic (polymorphic) as 12 possible - the compiler will infer the "Most 11 general type". For example, TheMarko's 10 example swap is polymorphic by default in 9 the absence of a type signature:

*Main> let 8 swap (a,b) = (b,a)
*Main> :t swap
swap 7 :: (t, t1) -> (t1, t)

As for partial 6 specialization, ghc has a non-98 extension:

Also, note 5 that there's a mismatch in terminology. What's 4 called generic in c++, Java, and C# is called 3 polymorphic in Haskell. "Generic" in 2 Haskell usually means polytypic: http://haskell.readscheme.org/generic.html
But, aboe 1 i use the c++ meaning of generic.

Score: 6

In Haskell you would create type classes. Type 18 classes are not like classes in OO languages. Take 17 the Numeric type class It says that anything 16 that is an instance of the class can perform 15 certain operations(+ - * /) so Integer is 14 a member of Numeric and provides implementations 13 of the functions necessary to be considered 12 Numeric and can be used anywhere a Numeric 11 is expected.

Say you want to be able to 10 foo Ints and Strings. Then you would declare 9 Int and String to be instances of the type 8 class Foo. Now anywhere you see the type 7 (Foo a) you can now use Int or String.

The 6 reason why you can't add ints and floats 5 directly is because add has the type (Numeric 4 a) a -> a -> a a is a type variable and 3 just like regular variables it can only 2 be bound once so as soon as you bind it 1 to Int every a in the list must be Int.

Score: 2

After reading enough in a Haskell book to 4 really understand Earwicker's answer I'd 3 suggest you also read about type classes. I'm 2 not sure what “partial specialization” means, but 1 it sounds like they could come close.

More Related questions