uebung2017_2/src/Aufgabe3.md

Aufgabe 3

module Aufgabe3 where

import FunPB  
import DataPB  
import AreaCode
import Data.Char  

Functor – ein Container?

Zur Erinnerung:

class Functor f where  
  fmap :: (a -> b) -> f a -> f b  

Aus der Vorlesung 2 kennen Sie bereits die Functor-Instanzen für [], Identity und einen binären Baum. Außerdem haben Sie gelernt, dass Sie auch für Ihre eigenen Typen Functor-Instanzen definieren können. Eine Intuition dafür, ob sich für einen Typ eine Functor-Instanz schreiben lässt, erhalten Sie, indem Sie sich fragen, ob der Typ "eine Art Container" ist, auf deren Inhalte sich Funktionen (a -> b) anwenden lassen. Was bedeutet dies in Haskell-Syntax? Hierfür ist es dienlich, sich den type constructor des betreffenden Datentyps anzuschauen. Handelt es sich um einen polymorphen Datentyp stehen die Chancen gut, dass es ein Functor ist.

data Bool = False | True  

data Maybe a = Nothing | Just a  

data (,) a b = (a,b)  

Bool ist offenbar kein Functor, denn der Typkonstruktor Bool hat keine Parameter – hier ist nur Platz für True und False. Maybe a dagegen hat einen Parameter, einen freien Slot für alles mögliche. Der Tupeltyp (,) a b hat sogar zwei Parameter – er kann Dinge von zwei verschiedenen Typen enthalten. Hier stellt sich die Frage, für welchen Container die Functorinstanz definiert ist. Ähnlich wie Funktionen, lassen sich auch Typkonstruktoren partiell anwenden. Für die Instanziierung werden dem Typkonstruktor daher alle bis auf ein Parameter übergeben. Dieser letzte, freie Parameter legt dann den Inhalt des "Container" fest. Beispiel:

instance Functor ((,) a) where --Die Functor-Instanz ist für (,) a definiert
    fmap f (x,y) = (x, f y)    --Also wird über Tupelslot 2 "gemapt"

Implementieren Sie Functor-Instanzen für die folgenden Datentypen:

data Vielleicht a = Nichts | Etwas a  
    deriving (Show,Eq)  

instance Functor Vielleicht where  
   fmap = undefined  


data Entweder a b = Jenes a | Dieses b  
    deriving (Show,Eq)  

instance Functor (Entweder a) where  
    fmap = undefined  


data Konstant a b = Konstant a  
    deriving (Show,Eq)  

instance Functor (Konstant a) where  
    fmap = undefined  

Achtung: Die "Container"-Metapher hat ihre Grenzen. Betrachten Sie hierzu noch einmal den Datentyp Pred a von Zettel 1: data Pred a = Pred (\a -> Bool).

data Pred a = Pred (a -> Bool)  
 runPred :: Pred a -> (a -> Bool)  
 runPred (Pred p) = p  

Pred a macht den Anschein als handele es sich auch hier um einen Container mit Inhalt a. Trotzdem lässt sich Functor hierfür nicht instanziieren. Der Unterschied liegt darin, dass der Typaramter a als Input und nicht als Ergebnis in der vom Konstruktor Pred "eingepackten" Berechnung auftaucht. Allerdings lässt sich hier auf eine sehr ähnliche Eigenschaft abstrahieren, die wir für's Erste InputFunctor nennen wollen.

class InputFunctor f where
    inputmap :: (a -> b) -> f b -> f a

Schreiben Sie eine InputFunctor-Instanz für Pred a.

instance InputFunctor Pred where  
    inputmap = undefined  

Hiermit lässt sich nun bequem die folgende Funktion definieren, welche aus einem Pred Int ein Pred String macht, das prüft, ob ein Eingabestring wenigstens die Länge 5 hat.

atLeast5 :: Pred Int  
atLeast5 = Pred $ (\x -> x>=5)  

atLeast5Char :: Pred String  
atLeast5Char = inputmap length atLeast5  

Functorial phone book

Jetzt noch einmal zurück zu PhoneBook aus Aufgabe 1.

type Number = String  
type Name = String  
type Entry = [Number]  

newtype PhoneBook = PB (Name -> Entry)  

PhoneBook hat keinen Parameter, aber die allgemeinere Version FunPB hat sogar zwei:

  data FunPB a b = FunPB (a -> (a,[b]))  

Beachten Sie, dass sich auch der Rückgabetyp ein wenig unterscheidet. Die Idee ist, dass FunPB zusätzlich zu den assoziierten Numbers (angenommen b ist Number) auch den gesuchten Name (angenommen a ist Name) zurückgibt.

Implementieren Sie eine Functor-Instanz für FunPB. Hinweis: Sie können benutzen, dass für [], ((,) a) und sogar für den "function arrow" ((->) a) bereits Functor-Instanzen in der GHC.Base existieren.

instance Functor (FunPB a) where  
    fmap = undefined  

Die Functor-Instanz erlaubt uns nun die Funktionen separateAreaCode :: Number -> (AreaCode,Number) und snd zu verwenden, um ein TelefonBuch mit separiertem bzw. ganz ohne AreaCode zu erhalten.

areaCodeFunPB :: FunPB Name Number -> FunPB Name (AreaCode,Number)  
areaCodeFunPB = fmap separateAreaCode  

withoutAreaCodeFunPB :: FunPB Name Number -> FunPB Name Number  
withoutAreaCodeFunPB = fmap (snd.separateAreaCode)  

result = "Suche \"Paula\" in (FunPB Name Number): \n"  
      ++ (show $ runFunPB (dataToFunPB simpleData) "Paula") ++ "\n"  
      ++ "Suche \"Paula\" in (FunPB Name (AreaCode,Number)): \n"  
      ++ (show $ runFunPB (areaCodeFunPB $ dataToFunPB simpleData) "Paula") ++ "\n"  
      ++ "Suche \"Paula\" in (FunPB Name Number) ohne Vorwahl: \n"  
      ++ (show $ runFunPB (withoutAreaCodeFunPB $ dataToFunPB simpleData) "Paula")