Algebraiske datatyper

fredag 2. juli 2010 Erlang F# Clojure Funksjonell programmering

I de programmeringsspråkene vi kaller funksjonelle språk har vi normalt ikke objekter. Det finnes språk som støtter flere paradigmer, men objekter er ikke en del av den funksjonelle. Vi har likevel behov for noe som minner om objekter; en form for entiteter eller typer som har definerte felt, som funkjonene kan jobbe på.

Vi kaller dem algebraiske datatyper, og det finnes mange varianter. De vanligste minner gjerne om structs i C eller lignende språk, og i mange språk (spesielt dynamiske) bruker vi gjerne assosiative arrays på samme måte. Her skal jeg sammenligne om noen av de algebraiske datatypene jeg har møtt i min ferd gjennom den funksjonelle programmeringsverdenen.

algebra

records i Erlang

Når vi programmerer i Erlang bruker vi ofte tupler til å holde data som er relatert til hverandre. En tupel er et sett med verdier i en bestemt rekkefølge. Posisjonene har derimot ikke noe navn, og det blir derfor tungvindt og lite lesbart å bruke lange tupler med mange verdier.

For å bøte på dette har Erlang en datatype som heter record. En record er en tupel hvor hver posisjon har et navn, og verdiene kan aksesseres ved hjelp av det navnet. Her er et eksempel på definering av en record-type, opprettelse av "instanser" av typen, og bruk av den:

11 % a record to store person information
12 -record(person, {givenname, surname, age}).
13
14 people() -> % some billionares...
15 [
16     #person{givenname = "Bill", surname = "Gates", age = 55},
17     #person{givenname = "Ed", surname = "Bass", age = 65},
18     #person{givenname = "David", surname = "Geffen", age = 67}
19 ].
20
21 full_name(P) ->
22 string:join([P#person.surname, P#person.givenname], ", ").
23
24 run() ->
25 % Prints a nice list of billionares over 60
26 % Using a list comprehension to filter and loop
27 [io:fwrite("~p~n", [full_name(P)])
28     || P <- people(), P#person.age >= 60].

Run-metoden skriver linjene "Bass, Ed" og "Geffen, David" til konsollet. Bruken av person-recorden er som du ser nesten som om det var et objekt i et OO-språk.

Erlangs record-type har fått mye kritikk. Record er egentlig bare syntaktisk sukker som ble tilført språket ganske sent, og det er tungvindt å bruken den. Som du ser må man spesifisere record-typen (person) hver gang man aksesserer en verdi. Dette er fordi runtime egentlig ikke vet at det er en person – den oppfatter datatypen som en helt vanlig tuple.

StructMap i Clojure

Clojure har noe som ligner veldig på Erlangs record, og her heter det StructMap. Som navnet tilsier er det en slags blanding av en struct og et map (dictionary/hashtable/assosiativt array). Her er eksempelet fra Erlang oversatt til Clojure:

119 ; a StructMap for person information
120 (defstruct person :givenname :surname :age)
121
122 (def people [ ; some billionares...
123              (struct person "Bill" "Gates" 55)
124              (struct person "Ed" "Bass" 65)
125              (struct person "David" "Geffen" 67)])
126
127 ; defining some nice functions to access specific keys
128 ; not strictly needed, but will make lookup faster..
129 (def givenname (accessor person :givenname))
130 (def surname (accessor person :surname))
131 (def age (accessor person :age))
132
133 (defn full-name [p]
134       "A function that will format a persons full name"
135       (str (surname p) ", " (givenname p)))
136
137
138 ; Print a nice list of billionares over 60
139 ; Using the doseq list comprehension
140 (doseq [p people :when (>= (age p) 60)]
141        (println (full-name p)))

Hovedforskjellen fra Erlang er at man ikke trenger å spesifisere feltnavnene når man oppretter "instanser" av en StructMap. Man trenger heller ikke fortelle hvilken StructMap en verdi er når man skal hente ut felt.

I eksempelet her har jeg definert accessor-funksjoner som henter ut verdiene fra de ulike feltene – dette er en optimaliseringssak, og er ikke nødvendig. (:surname p) vil fungere akkurat som (surname p), men det går litt saktere (ifølge dokumentasjonen).

records i F#

F# (og OCaml etc.) har også en type vi kaller record. I motsetning til Erlang og Clojure har F# ingen dynamisk typing, og du ser derfor at jeg må spesifisere datatypen for hvert felt når jeg deklarerer Person nedenfor. Derimot har F# utmerket type inference, og jeg behøver derfor ikke å spesifisere "Person" hverken når jeg oppretter eller bruker Person-instanser – F# utleder hvilken type det er basert på feltnavnene jeg bruker.

1 // a record to store person information
2 type Person = { GivenName : string; Surname : string; Age : int; }
3
4 let people = [ // a list of billionares
5     { GivenName = "Bill"; Surname = "Gates"; Age = 55 };
6     { GivenName = "Ed";    Surname = "Bass";   Age = 65 };
7     { GivenName = "David"; Surname = "Geffen"; Age = 67 }]
8
9 let full_name person = // format the name
10     person.Surname + ", " + person.GivenName
11
12 // using a list comprehension to filter on age
13 // it's OVERKILL, but I really wanted to show it off \o/
14 let over60 = seq { for p in people do if p.Age >= 60 then yield p }
15
16 // iterate over sequence and print the full name of each
17 Seq.iter (fun p -> System.Console.WriteLine (full_name p)) over60

F# har en annen algebraisk datatype som kalles Discriminated Union som man også bør ta en titt på (Haskell har det samme mener jeg). For en mere grunnleggende forståelse av disse typene anbefaler jeg å lese om algebraiske datayper på wikiperia.

Og mm noen skulle sitte på info om tilsvarende typer i Scala, Prolog eller andre språk jeg ikke har nevnt, er det bare å dele i kommentarfeltet.