SHARE
TWEET

Untitled

a guest Mar 26th, 2020 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Functors
  2.  
  3. Exercise 1.
  4.  
  5. You may recall the function map, which applies a function to each element of a list:
  6.  
  7. map :: (a -> b) -> [a] -> [b]
  8.  
  9. write a similar function mapMaybe that uses a provided function to transform the contents, if any, of a Maybe a.
  10. Don't forget to give it a type signature!
  11.  
  12. suggested solution:
  13.  
  14. mapMaybe f Nothing = Nothing
  15. mapMaybe f (Just x)
  16.  
  17. (Slide)
  18.  
  19. If you wrote out the type signature for mapMaybe, you'll notice that it's quite similar to the type of map
  20.  
  21. map      :: (a -> b) -> [a]     -> [b]
  22. mapMaybe :: (a -> b) -> Maybe a -> Maybe b
  23.  
  24. Both of these are polymorphic in the type of the contents of the container - you can map over a list of strings or a list of ints, or any [a], as long as you have a function that takes the appropriate type to transform with.
  25.  
  26. We can take it up a notch. What if we wanted a single map function that not only works for any type of contents, but any type of container? Then we could call that function on a list, or a maybe, or
  27. anything for which it makes sense to transform each of the elements. It should work like this:
  28.  
  29. > mapAnything (+1) [1,2,3]
  30. [2,3,4]
  31.  
  32. > mapAnything (+1) $ Just 1
  33. Just 2
  34.  
  35. > mapAnything (+1) Nothing
  36. Nothing
  37.  
  38. (Slide)
  39.  
  40. What would the type of such a function be?
  41.  
  42. mapAnything :: (a -> b) -> f a -> f b
  43.  
  44. Here, we introduce a new type parameter, f. f stands in for something like [] or Maybe - the container. More precisely, f stands in for some *type constructor*.
  45.  
  46. If we try to implement this function, we won't be able to - there's no way to do it generically for any f.
  47.  
  48. Instead, we can create a typeclass:
  49.  
  50. class Container f where
  51.         mapAnything :: (a -> b) -> f a -> f b
  52.  
  53. Then we make any container we want to map over an instance of this typeclass.
  54.  
  55. instance Container [] where
  56.         mapAnything = map
  57.  
  58. instance Container Maybe where
  59.         mapAnything = mapMaybe
  60.  
  61. And voila! We have a function mapAnything that works on any Container we've defined an instance for!
  62.  
  63. In fact, we don't need this typeclass. It's provided by the standard library. It's called Functor, and mapAnything is called fmap (the f is short for functor). Functor is very commonly used in haskell - most container types will have a Functor instance.
  64.  
  65. aside: whilst thinking of Functors as containers is a great starting intuition, there are some functors for which this metaphor becomes a bit less accurate. For example, there is a functor instance for for (r ->), the type of functions taking some type r. While you *can* think of a function as a sort of "container of a return value to be determined", doing so is a bit of a stretch.
  66.  
  67. > fmap (+1) [1,2,3]
  68. [2,3,4]
  69.  
  70. Exercise 2.
  71. Write a Functor instance for the binary tree data type. It should apply the given function to the value at each node, and not add or remove any nodes.
  72.  
  73. (starting code)
  74. data Tree a = Node a (Tree a) (Tree a) | Leaf
  75.  
  76. (suggested solution)
  77. instance Functor Tree where
  78.         fmap _ Leaf = Leaf
  79.         fmap f (Node x lt rt) = Node (f x) (fmap f lt) (fmap f rt)
  80.  
  81. Exercise 3.
  82. Write a function
  83.  
  84. exclaim :: Tree (Maybe [String]) -> Tree (Maybe [String])
  85.  
  86. that adds an exclamation mark to the end of each inner string.
  87.  
  88. (suggested solution)
  89.  
  90. exclaim :: Tree (Maybe [String]) -> Tree (Maybe [String])
  91. exclaim = (fmap . fmap . fmap) (++"!")
  92.  
  93. (slide)
  94. An aside - kinds and higher kinded polymorphism
  95.  
  96. The polymorphism of the f type parameter is more abstract than the polymorphism we have seen so far. We've seen type parameters standing in for concrete types like "Int", "String", or "[String]", but not type *constructors* like [] and Maybe.
  97.  
  98. We need a way of distinguishing between these *types of types* - we call them "kinds". Concrete types like "Int", for which we can create values, are of kind "*". Type constructors can be thought of as functions at the type level - they take a single type parameter and return a type. For example if you give "Maybe" an "Int", you get a "Maybe Int". We therefore write the kind of type constructors similarly to the types of functions - type constructors are of kind "* -> *" - in other words they take a concrete type, and return a concrete type.
  99.  
  100. Since this f parameter is a type constructor, it has kind (* -> *). Polymorphism in parameters with kinds other than "*" is known as "higher kinded polymorphism", and it sets haskell apart from many other languages. It offers serious abstraction power and code reuse, at the cost of sometimes being difficult to understand.
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top