Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Protcols, Functors and Type Classes

No description
by

Creighton Kirkendall

on 10 September 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Protcols, Functors and Type Classes

module type

TYPE
=

sig

type
t

end

module type

ADDABLE
=

sig

type
t

val
plus: t -> t -> t

val
identity: t

end

module type

FOLDABLE
=

functor
(M :
TYPE
) ->

sig


type
el = M.t

and
highKind

val
fold : highKind -> (el -> el -> el) -> el -> el

end

module
IntAddable =

struct

type
t =
int

let
plus = (+)

let
identity = 0

end

module
StringAddable =

struct


type
t =
string

let
plus x y = x^y

let
identity = ""

end

module
ListFoldable =

functor
(M :
TYPE
) ->

struct

type
el = M.t

type
highKind = el list

let rec
fold (hk: highKind) (fn: el -> el -> el) (i: el) =

match
hx
with
[] -> i
| head::tail -> fold tail fn (fn i head)

end



module
Summation
(F :
FOLDABLE
)
(M :
ADDABLE)
=

struct

module
FM = F(M)

let
sum hk = FM.fold hk M.plus M.identity

end



module
SumLInt = Summation(ListFoldable)(IntAddable)
module
SumLString = Summation(ListFodable)(StringAddable)

let
sumInt = SumLInt.sum [1; 2; 3]
(* -> 6 *)
let
sumString = SumLString.sum ["a"; "b"; "c"]
(* -> "abc" *)




type
'a
tree
=
Tip
|
Node
of 'a
tree
* 'a * 'a
tree



module
TreeFoldable =

functor
(M :
TYPE
) ->

struct

type
el = M.t

type
hk = el tree

let rec
fold (x : hk) (f: el -> el -> el) (i: el) =

match
x
with

Tip
-> i
|
Node
(left, e, right) -> fold right f (fold left f (f i e))

end


module
SumTInt = Summation(TreeFoldable)(IntAddable)

let
sumTree = SumTInt.sum(
Node
(
Node
(
Tip
, 3,
Tip
), 4,
Node
(
Tip
, 5,
Tip
)))
(* -> 12 *)
(
ns

higherkind
)

(
defprotocol

Addable
(
plus
[a b] )
(
ident
[a] ))

(
defprotocol

Foldable
(
fold
[l f i])
(
head
[l]))

(
extend-protocol

Addable

java.lang.Number
(
plus
[a b] (+ a b))
(
ident
[a] 0)

java.lang.String
(
plus
[a b] (str a b))
(
ident
[a] "")
nil
(
plus
[a b] b)
(
ident
[a] nil))

(
extend-protocol

Foldable
clojure.lang.IPersistentCollection
(
fold
[l f i] (reduce f i l))
(
head
[l] (first l)))


(
defn

sum
[data]
(
fold
data #(
plus
%1 %2) (
ident
(
head
data))))


(
sum
["a" "b" "c"])
; -> "abc"
(
sum
[ 1 2 3 ])
; -> 6


(
defrecord

Tree
[left elm right])


(
extend-protocol

Foldable

Tree
(
fold
[l f i]
(
fold
(
:right
l) f (
fold
(
:left
l) f (f i (
:elm
l)))))
(
head
[l]
(if (=
:tip
(
:right
l)) (
:elm
l) (
head
(
:right
l))))

Object
(
fold
[l f i] i)
(
head
[l] nil)))

(def my-tree (
Tree.
(
Tree.

:tip
3
:tip
) 4 (
Tree.

:tip
5 :
tip
)))
(
sum
my-tree) ;-> 12
Clojure
Ocaml
Haskell
class

Addable
a
where
plus :: a -> a -> a
identity :: a

class

Foldable
m
where

fold :: m el -> (el -> el -> el) -> el -> el


instance

Addable Int

where
plus x y = x + y
identity = 0

instance

Addable [a]

where
plus x y = x ++ y
identity = []

instance
Foldable []

where

fold [] f x = x
fold (h:t) f x = fold t f (f x h)




sum
:: (
Addable
a,
Foldable
m) => m a -> a
sum
hk = fold hk plus identity




main
:: IO ()
main
=
do


let
x = [ 1::Int, 2, 3]
y = ["a", "b", "c"]
print (sum x)
-- 6
print (sum y)
-- "abc"



data

Tree
a =
Tip
|
Node
(
Tree
a) a (
Tree
a)

deriving

Show


instance

Foldable Tree

where
fold Tip x f = x
fold (Node left el right) f i = fold right f (fold left f (f i el))

main
:: IO ()
main
= do

let
z =
Node
(
Node

Tip
4
Tip
) (3::
Int
) (
Node

Tip
5
Tip
)
print (sum z)
-- 12
Scala
trait

Addable
[T] {

def
plus(a: T, b: T): T

def
append: T
}

trait

Foldable
[F[_]] {

def
fold[A](data: F[A], fn: (A, A) => A, i: A): A
}


object

Summation
{

implicit object

IntAddable

extends

Addable
[Int] {

override def
append(a:
Int
, b:
Int
):
Int
= a + b

override def
identity = 0
}


implicit object

StringAddable

extends

Addable
[String] {

override def
append(a:
String
, b:
String
):
String
= a + b

override def
identity = ""
}



implicit object

FoldableList

extends

Foldable
[List] {

override def
fold[A](data:
List
[A], fn: (A, A) => A, i: A): A = data.foldLeft(i)(fn)
}






def
sum[M[_], A](data: M[A])(
implicit
m:
Addable
[A], f:
Foldable
[M]) = {
f.fold(data, m.plus, m.identity)
}





}
object

MyLib

extends

App
{

import

Summation
._




val
x =
List
(1, 2, 3)

val
y =
List
("a", "b", "c")
println(sum(x)) // 6
println(sum(y)) // "abc"





abstract class

Tree
[T]

case class

Tip
[T]
extends

Tree
[T]

case class

Node
[T](l:
Tree
[T], e:T, r:
Tree
[T])
extends

Tree
[T]





implicit object

FoldLeftTree

extends

Foldable
[
Tree
] {

override def
fold[A, B](xs: Tree[A], f: (B,A)=>B, i: B): B = {
xs
match
{

case
Tip
() => i

case
Node
(left,e,right) => fold(right, f, fold(left,f, f(b, e)))
}
}
}

val
z =
Node
(
Node
(
Tip
(), 3,
Tip
()), 4,
Node
(
Tip
(), 5,
Tip
()))
println(sum[
Tree
,
Int
](z)) // 12

}
Protocols, Functors and Type Classes
Solving the Expression Problem
Creighton Kirkendall
Data
Library
The Problem
Twitter: @crkirkendall
Email: ckirkendall@gmail.com
GitHub: http://github.com/ckirkendall
Systems Evolution Inc.
λ
Questions
?
Data
Library
Standard OO
Data
Library
Functional
Data
Library
The Problem
1
2
4
1
2
3
= 6
Summation
2
a
c
b
= "abc"
Requires:
Addable
Foldable
What is this about?
Building libraries.

The expression problem.

fundamental difference between Standard OO and Functional worlds.


Take Aways
Library developers have to plan to be extendable.

Functional OO is about extending libraries vs wrapping data.

While certain languages offer diffrent features the basic concept is the same.
Full transcript