Function Applicative for Great Good of Leap Year Function
pjschwarz
61 views
25 slides
Aug 14, 2024
Slide 1 of 25
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
About This Presentation
This deck is about the leap_year function shown in https://x.com/Iceland_jack/status/1802659835642528217, i.e.
leap_year :: Integral a => a -> Bool
leap_year = liftA2 (>) (gcd 80) (gcd 50)
Given an integer representing a year, the function returns a boolean indicating if that year is a l...
Slide Content
FunctionApplicativefor Great Good
of Leap Year Function
Polyglot FPfor Fun and Profit –Haskelland Scala
K
Starling
�??????���??????��
Kestrel
B
S
PhoenixΦ
leap_year :: Integral a => a -> Bool
leap_year = liftA2 (>) (gcd 80) (gcd 50)
liftA2 f g = S (B f g)
liftA2 = Φ
liftA2 f g h = S (S (K f) g) h
@philip_schwarzslides by https://fpilluminated.com/
of Leap Year Function
Polyglot FPfor Fun and Profit –Haskelland Scala
K
Starling
�??????���??????��
Kestrel
B
S
PhoenixΦ
leap_year :: Integral a => a -> Bool
leap_year = liftA2 (>) (gcd 80) (gcd 50)
liftA2 f g = S (B f g)
liftA2 = Φ
liftA2 f g h = S (S (K f) g) h
@philip_schwarzslides by https://fpilluminated.com/
Thisdeckisabouttheleap_yearfunctionshowninthetweetbelow.ItisbeingdefinedinaHaskellREPL.
Givenanintegerrepresentingayear,thefunctionreturnsabooleanindicatingifthatyearisaleapyear.
@philip_schwarz
https://x.com/Iceland_jack/status/1802659835642528217
Givenanintegerrepresentingayear,thefunctionreturnsabooleanindicatingifthatyearisaleapyear.
@philip_schwarz
https://x.com/Iceland_jack/status/1802659835642528217
Theleap_yearfunctionusesbuilt-infunctions(>)andgcd
-- Greater Than function
> :type (>)
(>) :: Ord a => a -> a -> Bool
>(>)2 3
False
> (>)3 2
True
-- Greatest Common Divisor function
> :type gcd
gcd:: Integrala => a -> a -> a
> gcd10 15
5
> gcd10 16
2
> gcd10 17
1
> gcd10 18
2
> gcd10 19
1
> gcd10 20
10
leap_year = liftA2 (>) (gcd 80) (gcd 50)
-- Greater Than function
> :type (>)
(>) :: Ord a => a -> a -> Bool
>(>)2 3
False
> (>)3 2
True
-- Greatest Common Divisor function
> :type gcd
gcd:: Integrala => a -> a -> a
> gcd10 15
5
> gcd10 16
2
> gcd10 17
1
> gcd10 18
2
> gcd10 19
1
> gcd10 20
10
leap_year = liftA2 (>) (gcd 80) (gcd 50)
> leap_year = liftA2 (>) (gcd 80) (gcd 50)
> :type leap_year
leap_year :: Integral a => a -> Bool
> leap_year 2024
True
> leap_year 2025
False
> fmap leap_year [1600, 1700, 1800, 1900, 2000, 2100, 2200, 2300, 2400]
[True,False,False,False,True,False,False,False,True]
leap_yearalsousesliftA2,whichisafunctionprovidedbyApplicative.
> import Control.Applicative
> :type liftA2
liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
Let’sdefineleap_yearandtakeitforaquickspin.
leap_year = liftA2 (>) (gcd 80) (gcd 50)
> :type leap_year
leap_year :: Integral a => a -> Bool
> leap_year 2024
True
> leap_year 2025
False
> fmap leap_year [1600, 1700, 1800, 1900, 2000, 2100, 2200, 2300, 2400]
[True,False,False,False,True,False,False,False,True]
leap_yearalsousesliftA2,whichisafunctionprovidedbyApplicative.
> import Control.Applicative
> :type liftA2
liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
Let’sdefineleap_yearandtakeitforaquickspin.
leap_year = liftA2 (>) (gcd 80) (gcd 50)
OperatorDefinition
¬�����
�∨�����
�∧������
�→�??????���ℎ���
�⟺��??????������??????�??????��
Thefollowingslideuseslogicoperators¬,∧,∨,→and⟺.
Hereisareminderoftheirdefinition.
¬�����
�∨�����
�∧������
�→�??????���ℎ���
�⟺��??????������??????�??????��
Thefollowingslideuseslogicoperators¬,∧,∨,→and⟺.
Hereisareminderoftheirdefinition.
Itlookslikeleap_yearisexploitingthealgorithm
describedinthefollowingtwitter/xthread.
leap_year = liftA2 (>) (gcd 80) (gcd 50)
https://x.com/chordbug/status/1497912619784720384/photo/1
https://x.com/chordbug/status/1497912619784720384
describedinthefollowingtwitter/xthread.
leap_year = liftA2 (>) (gcd 80) (gcd 50)
https://x.com/chordbug/status/1497912619784720384/photo/1
https://x.com/chordbug/status/1497912619784720384
Bytheway,incaseyouareaskingyourselfhowtheprevioussliderefactoredthis
�??????��??????�������⟺4|�∧¬100�∧¬400�))
tothis
�??????��??????�������⟺4|�∧(100�→400�)
seebelowforhowIexplainedittomyself.
IfweapplyDeMorgan’slaw,i.e.
¬�∧�=¬�∨¬�
to
¬100�∧¬400�))
weget
�??????��??????�������⟺4�∧¬(100�∨400|�))
Next,ifweapply¬�∨�=�→�
to
¬100�)∨400�)
weget
�??????��??????�������⟺4|�∧(100�→400�)
whichreadsasfollows:
�is a leap year if and only if both of the following are true
•it is divisible by 4
•if it is divisible by 100, then it is also divisible by 400
refactor
refactor
�??????��??????�������⟺4|�∧¬100�∧¬400�))
tothis
�??????��??????�������⟺4|�∧(100�→400�)
seebelowforhowIexplainedittomyself.
IfweapplyDeMorgan’slaw,i.e.
¬�∧�=¬�∨¬�
to
¬100�∧¬400�))
weget
�??????��??????�������⟺4�∧¬(100�∨400|�))
Next,ifweapply¬�∨�=�→�
to
¬100�)∨400�)
weget
�??????��??????�������⟺4|�∧(100�→400�)
whichreadsasfollows:
�is a leap year if and only if both of the following are true
•it is divisible by 4
•if it is divisible by 100, then it is also divisible by 400
refactor
refactor
Whyisitthat,givenfunctiondefinition
leap_year = liftA2 (>) (gcd 80) (gcd 50)
andgivensomeinputyear
e.g.2024
evaluatingleap_year year,amountstoevaluating
(gcd 80 year) > (gcd 50 year)
e.g.
(gcd 802024) > (gcd 502024)
?
leap_year = liftA2 (>) (gcd 80) (gcd 50)
andgivensomeinputyear
e.g.2024
evaluatingleap_year year,amountstoevaluating
(gcd 80 year) > (gcd 50 year)
e.g.
(gcd 802024) > (gcd 502024)
?
HereisthedefinitionofApplicativefunctionliftA2
https://hackage.haskell.org/package/base-4.20.0.1/docs/Prelude.html#liftA2
https://hackage.haskell.org/package/base-4.20.0.1/docs/Prelude.html#liftA2
Butgiventhatthesignatureof liftA2is
liftA2 :: (a -> b -> c) -> f a -> f b -> f c c
howdoes
liftA2 (>) (gcd 80) (gcd 50) 2024
mapto
(gcd 80 2024) > (gcd 50 2024)
?
Thefirststepthatwearegoingtotaketoanswerthisquestion,istoconsidertheactualparametersofliftA2in
liftA2 (>) (gcd 80) (gcd 50) 2024
Thefirstone,i.e.(>),isafunctionwithtypeInt->Int->Bool.
Thesecondone,i.e.(gcd 80)istheresultofapplyingafunctionoftypeInt->Int->Intto80,whichresultsina
functionInt->Int.
Thethirdone,i.e.(gcd 50)istheresultofapplyingafunctionoftypeInt->Int->Intto50,whichalsoresultsina
functionInt->Int.
Giventhatthetypeofleap_yearisInt -> Bool,itfollowsthatin
liftA2 (>) (gcd 80) (gcd 50) 2024
thesignatureofliftA2is
liftA2 :: (Int -> Int -> Bool) -> (Int -> Int) -> (Int -> Int) -> (Int -> Bool)
leap_year = liftA2 (>) (gcd 80) (gcd 50)
liftA2 :: (a -> b -> c) -> f a -> f b -> f c c
howdoes
liftA2 (>) (gcd 80) (gcd 50) 2024
mapto
(gcd 80 2024) > (gcd 50 2024)
?
Thefirststepthatwearegoingtotaketoanswerthisquestion,istoconsidertheactualparametersofliftA2in
liftA2 (>) (gcd 80) (gcd 50) 2024
Thefirstone,i.e.(>),isafunctionwithtypeInt->Int->Bool.
Thesecondone,i.e.(gcd 80)istheresultofapplyingafunctionoftypeInt->Int->Intto80,whichresultsina
functionInt->Int.
Thethirdone,i.e.(gcd 50)istheresultofapplyingafunctionoftypeInt->Int->Intto50,whichalsoresultsina
functionInt->Int.
Giventhatthetypeofleap_yearisInt -> Bool,itfollowsthatin
liftA2 (>) (gcd 80) (gcd 50) 2024
thesignatureofliftA2is
liftA2 :: (Int -> Int -> Bool) -> (Int -> Int) -> (Int -> Int) -> (Int -> Bool)
leap_year = liftA2 (>) (gcd 80) (gcd 50)
Butwhatabstractiondoesfneedtobeinorderfor
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
tobecome
liftA2 :: (Int -> Int -> Boolean) -> (Int -> Int) -> (Int -> Int) -> (Int -> Boolean)
?
Letusdefineftobeafunctionoftyper -> ?,whererissomespecifictype,and?issomeyettobespecifiedtype.
Nowlet’supdatethesignatureofliftA2toreflecttheabovedefinitionoff:
liftA2 :: (a -> b -> c) -> (r -> ?1) -> (r -> ?2) -> (r -> ?3)
Inthecaseathand,i.e.
liftA2 (>) (gcd 80) (gcd 50) 2024
wealreadyknowthat
1.(a -> b -> c)is(Int -> Int -> Bool), i.e. the type of (>),
2.(r -> ?3) is (Int -> Boolean), i.e. the type of leap_year
3.(r -> ?1) and (r -> ?2) are (Int -> Int), i.e. the type of both (gcd 80) and (gcd 50)
soweseethatwithr=Int,?1=Int,?2=Intand?3=Bool,thesignatureofliftA2isindeedthesoughtone:
liftA2 :: (Int -> Int -> Bool) -> (Int -> Int) -> (Int -> Int) -> (Int -> Bool)
leap_year = liftA2 (>) (gcd 80) (gcd 50)
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
tobecome
liftA2 :: (Int -> Int -> Boolean) -> (Int -> Int) -> (Int -> Int) -> (Int -> Boolean)
?
Letusdefineftobeafunctionoftyper -> ?,whererissomespecifictype,and?issomeyettobespecifiedtype.
Nowlet’supdatethesignatureofliftA2toreflecttheabovedefinitionoff:
liftA2 :: (a -> b -> c) -> (r -> ?1) -> (r -> ?2) -> (r -> ?3)
Inthecaseathand,i.e.
liftA2 (>) (gcd 80) (gcd 50) 2024
wealreadyknowthat
1.(a -> b -> c)is(Int -> Int -> Bool), i.e. the type of (>),
2.(r -> ?3) is (Int -> Boolean), i.e. the type of leap_year
3.(r -> ?1) and (r -> ?2) are (Int -> Int), i.e. the type of both (gcd 80) and (gcd 50)
soweseethatwithr=Int,?1=Int,?2=Intand?3=Bool,thesignatureofliftA2isindeedthesoughtone:
liftA2 :: (Int -> Int -> Bool) -> (Int -> Int) -> (Int -> Int) -> (Int -> Bool)
leap_year = liftA2 (>) (gcd 80) (gcd 50)
So,toarriveattheliftA2signaturethatisapplicablein
liftA2 (>) (gcd 80) (gcd 50) 2024
i.e.
liftA2 :: (Int -> Int -> Bool) -> (Int -> Int) -> (Int -> Int) -> (Int -> Bool)
wefirsttaketheminimaldefinitionofFunctor
class Functor f where
fmap :: (a -> b) -> f a -> f b
and a minimal definition of Applicative, but with liftA2added to it
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
WethentaketheFunctionFunctorandFunctionApplicative,i.e.theFunctorandApplicativeinstancesfor((->) r),
inwhichfisdefinedtobeafunctionfromsomespecifictypertosomeyetunspecifiedtype.Herearethefunction
signaturesoftheresultinginstances:
fmap :: (a -> b) -> (r -> a) -> (r -> b)
pure :: a -> (r -> a)
(<*>) :: (r -> a -> b) -> (r -> a) -> (r -> b)
liftA2 :: (a -> b -> c) -> (r -> a) -> (r -> b) -> (r -> c)
If we define r = Int, a = Int, b = Intand c = Bool, then liftA2 takes on the desired signature:
liftA2 :: (Int -> Int -> Bool) -> (Int -> Int) -> (Int -> Int) -> (Int -> Bool)
liftA2 (>) (gcd 80) (gcd 50) 2024
i.e.
liftA2 :: (Int -> Int -> Bool) -> (Int -> Int) -> (Int -> Int) -> (Int -> Bool)
wefirsttaketheminimaldefinitionofFunctor
class Functor f where
fmap :: (a -> b) -> f a -> f b
and a minimal definition of Applicative, but with liftA2added to it
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
WethentaketheFunctionFunctorandFunctionApplicative,i.e.theFunctorandApplicativeinstancesfor((->) r),
inwhichfisdefinedtobeafunctionfromsomespecifictypertosomeyetunspecifiedtype.Herearethefunction
signaturesoftheresultinginstances:
fmap :: (a -> b) -> (r -> a) -> (r -> b)
pure :: a -> (r -> a)
(<*>) :: (r -> a -> b) -> (r -> a) -> (r -> b)
liftA2 :: (a -> b -> c) -> (r -> a) -> (r -> b) -> (r -> c)
If we define r = Int, a = Int, b = Intand c = Bool, then liftA2 takes on the desired signature:
liftA2 :: (Int -> Int -> Bool) -> (Int -> Int) -> (Int -> Int) -> (Int -> Bool)
Nowlet’sgetbacktothequestionthatwearelookingtoanswer.
Whyisitthatgivenfunctiondefinition
leap_year = liftA2 (>) (gcd 80) (gcd 50)
andgivensomeinputyear,evaluatingleap_year year,amountstoevaluating
(gcd 80 year) > (gcd 50 year)
?
Orinotherwords,sinceleap_yearisdefinedintermsofliftA2,whyisitthat
liftA2 (>) (gcd 80) (gcd 50) year
evaluatesto
(gcd 80 year) > (gcd 50 year)
?
Whyisitthatgivenfunctiondefinition
leap_year = liftA2 (>) (gcd 80) (gcd 50)
andgivensomeinputyear,evaluatingleap_year year,amountstoevaluating
(gcd 80 year) > (gcd 50 year)
?
Orinotherwords,sinceleap_yearisdefinedintermsofliftA2,whyisitthat
liftA2 (>) (gcd 80) (gcd 50) year
evaluatesto
(gcd 80 year) > (gcd 50 year)
?
ItturnsoutthattheliftA2functionoftheFunctionApplicativeisacombinatory
logicfunction(acombinator)calledthephoenix.
Toanswerthequestionrestatedinthepreviousslide,insteadoflookingatthecode
forliftA2,inthenextslidewearegoingtoexploitthefactthatliftA2=phoenix.
liftA2 :: (a -> b -> c) -> (r -> a) -> (r -> b) -> (r -> c)
Φ � � � �=�(� �)(� �)
Φ � � ℎ �=�(� �)(ℎ �)
�ℎ���??????�
https://hackage.haskell.org/package/data-aviary-0.4.0/docs/Data-Aviary-Birds.html
rename variables for additional clarity
Φ=λ�.λ�.λℎ.λ�.���ℎ�
make ‘point free’
logicfunction(acombinator)calledthephoenix.
Toanswerthequestionrestatedinthepreviousslide,insteadoflookingatthecode
forliftA2,inthenextslidewearegoingtoexploitthefactthatliftA2=phoenix.
liftA2 :: (a -> b -> c) -> (r -> a) -> (r -> b) -> (r -> c)
Φ � � � �=�(� �)(� �)
Φ � � ℎ �=�(� �)(ℎ �)
�ℎ���??????�
https://hackage.haskell.org/package/data-aviary-0.4.0/docs/Data-Aviary-Birds.html
rename variables for additional clarity
Φ=λ�.λ�.λℎ.λ�.���ℎ�
make ‘point free’
Φ=λ�.λ�.λℎ.λ�.���ℎ�
Equation Action
??????���_����=????????????���2>��� 80��� 50 ????????????���2=Φ
??????���_����=Φ>��� 80��� 50 Φ=λ�.λ�.λℎ.λ�.���ℎ�
??????���_����=λ�.λ�.λℎ.λ�.���ℎ�>��� 80��� 50 �=>
??????���_����=(λ�.λℎ.λ�.>��ℎ�)��� 80��� 50 �=��� 80
??????���_����=(λℎ.λ�.>���80�ℎ�)��� 50 ℎ=��� 50
??????���_����=λ�.>���80����50� >��=�>�
??????���_����=λ�.���80�>���50� apply ??????���_����to2024
??????���_����2024=(λ�.���80�>���50�) 2024 �=2024
??????���_����2024=���802024>���502024 Q.E.D.
Equation Action
??????���_����=????????????���2>��� 80��� 50 ????????????���2=Φ
??????���_����=Φ>��� 80��� 50 Φ=λ�.λ�.λℎ.λ�.���ℎ�
??????���_����=λ�.λ�.λℎ.λ�.���ℎ�>��� 80��� 50 �=>
??????���_����=(λ�.λℎ.λ�.>��ℎ�)��� 80��� 50 �=��� 80
??????���_����=(λℎ.λ�.>���80�ℎ�)��� 50 ℎ=��� 50
??????���_����=λ�.>���80����50� >��=�>�
??????���_����=λ�.���80�>���50� apply ??????���_����to2024
??????���_����2024=(λ�.���80�>���50�) 2024 �=2024
??????���_����2024=���802024>���502024 Q.E.D.
Thankstothephoenix,wehavenotneededtolookattheimplementationofliftA2inordertounderstandhowitworks.Still,whatdoes
theimplementationlooklike?Ituses<*>andfmap:
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2 f x = (<*>) (fmap f x)
It turns out that in the Function Functor, fmap is the Bluebird combinator, and
in the Function Applicative, <*> is the Starling combinator. So again,insteadof
lookingatthecodeforfmapand<*>,inthenextslidewearegoingtoexploitthefactthat fmap = bluebird and <*> = starling.
fmap :: (a -> b) -> (r -> a) -> (r -> b)
� � � �=�(� �) � � � �=�(� �)�??????���??????��
https://hackage.haskell.org/package/data-aviary-0.4.0/docs/Data-Aviary-Birds.html
�=λ�.λ�.�.���
(<*>) :: (r -> a -> b) -> (r -> a) -> (r -> b)
?????? � � �=(� �)(� �)?????? � � �=(� �)(� �)??????���????????????��??????=λ�.λ�.λ�.����
liftA2 f x = (<*>)(fmap f x)
liftA2 f g = S(B f g)
The function composition function. Given two functions �
and �, it returns a function ℎ that is � composed with �,
i.e. ℎ�=�(��). Also known as Compositor.
Also known as Distributor.
theimplementationlooklike?Ituses<*>andfmap:
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2 f x = (<*>) (fmap f x)
It turns out that in the Function Functor, fmap is the Bluebird combinator, and
in the Function Applicative, <*> is the Starling combinator. So again,insteadof
lookingatthecodeforfmapand<*>,inthenextslidewearegoingtoexploitthefactthat fmap = bluebird and <*> = starling.
fmap :: (a -> b) -> (r -> a) -> (r -> b)
� � � �=�(� �) � � � �=�(� �)�??????���??????��
https://hackage.haskell.org/package/data-aviary-0.4.0/docs/Data-Aviary-Birds.html
�=λ�.λ�.�.���
(<*>) :: (r -> a -> b) -> (r -> a) -> (r -> b)
?????? � � �=(� �)(� �)?????? � � �=(� �)(� �)??????���????????????��??????=λ�.λ�.λ�.����
liftA2 f x = (<*>)(fmap f x)
liftA2 f g = S(B f g)
The function composition function. Given two functions �
and �, it returns a function ℎ that is � composed with �,
i.e. ℎ�=�(��). Also known as Compositor.
Also known as Distributor.
Equation Action
??????���_����=????????????���2>��� 80��� 50 ????????????���2��=??????(���)
??????���_����=??????(�>���80)���50 ??????=λ�.λ�.λ�.� �� �
??????���_����=(λ�.λ�.λ�.����)(�>���80)���50 �=�>���80
??????���_����=(λ�.λ�.�>���80���)���50 �=��� 50
??????���_����=(λ�.�>���80����50�) �=λ�.λ�.λ�.�� �=λ�.λ�.λ�.�� �
??????���_����=(λ�.(λ�.λ�.λ�.���)>���80����50�) �=>
??????���_����=(λ�.(λ�.λ�.>��)���80����50�) �=���80
??????���_����=(λ�.(λ�.>���80�)����50�) �=�
??????���_����=(λ�.>���80����50�) >��=�>�
??????���_����=(λ�.���80�>���50�) apply ??????���_����to2024
??????���_����2024=λ�.���80�>���50�2024 �=2024
??????���_����2024=���802024>���502024 Q.E.D.
�=λ�.λ�.�.���??????=λ�.λ�.λ�.����liftA2 f g = S(B f g)
??????���_����=????????????���2>��� 80��� 50 ????????????���2��=??????(���)
??????���_����=??????(�>���80)���50 ??????=λ�.λ�.λ�.� �� �
??????���_����=(λ�.λ�.λ�.����)(�>���80)���50 �=�>���80
??????���_����=(λ�.λ�.�>���80���)���50 �=��� 50
??????���_����=(λ�.�>���80����50�) �=λ�.λ�.λ�.�� �=λ�.λ�.λ�.�� �
??????���_����=(λ�.(λ�.λ�.λ�.���)>���80����50�) �=>
??????���_����=(λ�.(λ�.λ�.>��)���80����50�) �=���80
??????���_����=(λ�.(λ�.>���80�)����50�) �=�
??????���_����=(λ�.>���80����50�) >��=�>�
??????���_����=(λ�.���80�>���50�) apply ??????���_����to2024
??????���_����2024=λ�.���80�>���50�2024 �=2024
??????���_����2024=���802024>���502024 Q.E.D.
�=λ�.λ�.�.���??????=λ�.λ�.λ�.����liftA2 f g = S(B f g)
In previous slides, we saw this definition of liftA2
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2 f x = (<*>) (fmap f x)
Here is the same definition, but using the infix operator equivalent of function fmap, and the infix operator equivalent of function (<*>).
liftA2 f g h = f <$> g <*> h x
The above is a more convenient version of the following:
liftA2 f g h = pure f <*> g <*> h
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap
https://hackage.haskell.org/package/base-4.20.0.1/docs/Control-Applicative.html
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2 f x = (<*>) (fmap f x)
Here is the same definition, but using the infix operator equivalent of function fmap, and the infix operator equivalent of function (<*>).
liftA2 f g h = f <$> g <*> h x
The above is a more convenient version of the following:
liftA2 f g h = pure f <*> g <*> h
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap
https://hackage.haskell.org/package/base-4.20.0.1/docs/Control-Applicative.html
OnthepreviousslidewesawthefollowingpossibleimplementationofliftA2
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2 f g h = pure f <*> g <*> h
In the Function Applicative, <*> is the Starling combinator that we saw
earlier, and pure is the Kestrel combinator. So again,insteadoflookingat
thecodeforpureand<*>,inthenextslidewearegoingtoexploitthefact
that pure = kestrel and <*> = starling.
pure :: a -> (r -> a)
??????� �=�?????? � �=�??????�����??????
https://hackage.haskell.org/package/data-aviary-0.4.0/docs/Data-Aviary-Birds.html
??????=λ�.λ�.�
(<*>) :: (r -> a -> b) -> (r -> a) -> (r -> b)
?????? � � �=(� �)(� �)?????? � � �=(� �)(� �)??????���????????????��??????=λ�.λ�.λ�.����
liftA2 f x = (<*>) (fmap f x)
liftA2 f g h = f <$> g <*> h
liftA2 f g h = pure f <*> g <*> h
liftA2 f g h = S (S (K f) g) h
Also known as
Cancellator.
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2 f g h = pure f <*> g <*> h
In the Function Applicative, <*> is the Starling combinator that we saw
earlier, and pure is the Kestrel combinator. So again,insteadoflookingat
thecodeforpureand<*>,inthenextslidewearegoingtoexploitthefact
that pure = kestrel and <*> = starling.
pure :: a -> (r -> a)
??????� �=�?????? � �=�??????�����??????
https://hackage.haskell.org/package/data-aviary-0.4.0/docs/Data-Aviary-Birds.html
??????=λ�.λ�.�
(<*>) :: (r -> a -> b) -> (r -> a) -> (r -> b)
?????? � � �=(� �)(� �)?????? � � �=(� �)(� �)??????���????????????��??????=λ�.λ�.λ�.����
liftA2 f x = (<*>) (fmap f x)
liftA2 f g h = f <$> g <*> h
liftA2 f g h = pure f <*> g <*> h
liftA2 f g h = S (S (K f) g) h
Also known as
Cancellator.
Equation Action
??????���_����=????????????���2>��� 80��� 50 ????????????���2��ℎ=??????????????????��ℎ
??????���_����=??????????????????>���80���50 ??????=λ�.λ�.λ�.� �� �
??????���_����=(λ�.λ�.λ�.����)????????????>���80���50 �=????????????>���80
??????���_����=(λ�.λ�.????????????>���80���)���50 �= ���50
??????���_����=λ�.????????????>���80����50� ??????=λ�.λ�.λ�.����=λ�.λ�.λ�.����
??????���_����=λ�.λ�.λ�.λ�.����??????>���80����50� �=(??????>)
??????���_����=λ�.(λ�.λ�.??????>���)���80����50� �= ���80
??????���_����=λ�.(λ�.??????>����80�)����50� �= �
??????���_����=λ�.??????>����80����50� K=λ�.λ�.�
??????���_����=λ�.(λ�.>)����80����50� �=>
??????���_����=λ�.(λ�.>)����80����50� �= �
??????���_����=λ�.(>)���80����50� >��=�>�
??????���_����=λ�.���80�>���50� apply ??????���_����to2024
??????���_����2024=λ�.���80�>���50�2024 �=2024
??????���_����2024=���802024>���502024 Q.E.D.
??????=λ�.λ�.�??????=λ�.λ�.λ�.����liftA2 f g h = S (S (K f) g) h
??????���_����=????????????���2>��� 80��� 50 ????????????���2��ℎ=??????????????????��ℎ
??????���_����=??????????????????>���80���50 ??????=λ�.λ�.λ�.� �� �
??????���_����=(λ�.λ�.λ�.����)????????????>���80���50 �=????????????>���80
??????���_����=(λ�.λ�.????????????>���80���)���50 �= ���50
??????���_����=λ�.????????????>���80����50� ??????=λ�.λ�.λ�.����=λ�.λ�.λ�.����
??????���_����=λ�.λ�.λ�.λ�.����??????>���80����50� �=(??????>)
??????���_����=λ�.(λ�.λ�.??????>���)���80����50� �= ���80
??????���_����=λ�.(λ�.??????>����80�)����50� �= �
??????���_����=λ�.??????>����80����50� K=λ�.λ�.�
??????���_����=λ�.(λ�.>)����80����50� �=>
??????���_����=λ�.(λ�.>)����80����50� �= �
??????���_����=λ�.(>)���80����50� >��=�>�
??????���_����=λ�.���80�>���50� apply ??????���_����to2024
??????���_����2024=λ�.���80�>���50�2024 �=2024
??????���_����2024=���802024>���502024 Q.E.D.
??????=λ�.λ�.�??????=λ�.λ�.λ�.����liftA2 f g h = S (S (K f) g) h
WehadagoatunderstandingthefollowingfunctionsoftheFunctionApplicative,withouttheneedtolook
attheircode:fmap,pure,<*>andliftA2.
Wedidthisbylookingattheirequivalentcombinators:Bluebird,Kestrel,StarlingandPhoenix.
WhilewehavenowseenthecodeforliftA2,wehavenotyetseenthatforfmap,pureand<*>.
Nowthewearefamiliarwiththecombinators,thecodeforfmap,pureand<*>doesnotpresentany
surprises,andcanbeseenonthefollowingslide,whichactsasarecapofthecorrespondencebetweenthe
functionsandthecombinators.
attheircode:fmap,pure,<*>andliftA2.
Wedidthisbylookingattheirequivalentcombinators:Bluebird,Kestrel,StarlingandPhoenix.
WhilewehavenowseenthecodeforliftA2,wehavenotyetseenthatforfmap,pureand<*>.
Nowthewearefamiliarwiththecombinators,thecodeforfmap,pureand<*>doesnotpresentany
surprises,andcanbeseenonthefollowingslide,whichactsasarecapofthecorrespondencebetweenthe
functionsandthecombinators.
instance Applicative ((->) r) where
pure x = (\_ -> x)
f <*> g = \x -> f x (g x)
liftA2 f x = (<*>) (fmap f x)
instance Functor ((->) r) where
fmap = (.)
B
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap
Starling
Kestrel ?????? � �=�
�??????���??????��� � � �=�� �
(<*>)
pure
fmap
(<$>)
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
class Functor f where
fmap :: (a -> b) -> f a -> f b
K
?????? � � �=(� �)(� �)S
Phoenix liftA2Φ � � ℎ �=�(� �)(ℎ �)Φ
pure x = (\_ -> x)
f <*> g = \x -> f x (g x)
liftA2 f x = (<*>) (fmap f x)
instance Functor ((->) r) where
fmap = (.)
B
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap
Starling
Kestrel ?????? � �=�
�??????���??????��� � � �=�� �
(<*>)
pure
fmap
(<$>)
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
class Functor f where
fmap :: (a -> b) -> f a -> f b
K
?????? � � �=(� �)(� �)S
Phoenix liftA2Φ � � ℎ �=�(� �)(ℎ �)Φ
The next slide shows the Scala code for the definition of leap_year in
terms of the following alternative equivalent implementations of liftA2:
liftA2 f x = (<*>) (fmap f x)
liftA2 f g h = f <$> g <*> h x
liftA2 f g h = pure f <*> g <*> h
terms of the following alternative equivalent implementations of liftA2:
liftA2 f x = (<*>) (fmap f x)
liftA2 f g h = f <$> g <*> h x
liftA2 f g h = pure f <*> g <*> h
for
leapYear <- List(leapYear1, leapYear2, leapYear3)
_ = assert(List.range(2000,2025).filter(leapYear) == List(2000, 2004, 2008, 2012, 2016, 2020, 2024))
_ = assert(List(1600, 1700, 1800, 1900, 2000).filter(leapYear) == List(1600, 2000))
yield ()
extension[A,B](f: A => B)
def`<$>`[F[_]: Functor](fa: F[A]): F[B] = fa.map(f)
importcats.*
importcats.implicits.*
valgcd: Int=> Int=> Int=
x => y => x.gcd(y).intValue
val`(>)`: Int=> Int=> Boolean=
x => y => x > y
valleapYear1: Int=> Boolean=
liftA2_v1(`(>)`)(gcd(80), gcd(50))
defliftA2_v1[A,B,C,F[_]: Applicative](f: A => B => C)(fa: F[A], fb: F[B]): F[C] =
fa.map(f) <*>fb
valleapYear3: Int=> Boolean=
liftA2_v3(`(>)`)(gcd(80), gcd(50))
valleapYear2: Int=> Boolean=
liftA2_v2(`(>)`)(gcd(80), gcd(50))
defliftA2_v2[A,B,C,F[_]: Applicative](f: A => B => C)(fa: F[A], fb: F[B]): F[C] =
f `<$>` fa <*> fb
defliftA2_v3[A,B,C,F[_]: Applicative](f: A => B => C)(fa: F[A], fb: F[B]): F[C] =
f.pure <*> fa <*> fb
import scala.math.BigInt.int2bigInt
leapYear <- List(leapYear1, leapYear2, leapYear3)
_ = assert(List.range(2000,2025).filter(leapYear) == List(2000, 2004, 2008, 2012, 2016, 2020, 2024))
_ = assert(List(1600, 1700, 1800, 1900, 2000).filter(leapYear) == List(1600, 2000))
yield ()
extension[A,B](f: A => B)
def`<$>`[F[_]: Functor](fa: F[A]): F[B] = fa.map(f)
importcats.*
importcats.implicits.*
valgcd: Int=> Int=> Int=
x => y => x.gcd(y).intValue
val`(>)`: Int=> Int=> Boolean=
x => y => x > y
valleapYear1: Int=> Boolean=
liftA2_v1(`(>)`)(gcd(80), gcd(50))
defliftA2_v1[A,B,C,F[_]: Applicative](f: A => B => C)(fa: F[A], fb: F[B]): F[C] =
fa.map(f) <*>fb
valleapYear3: Int=> Boolean=
liftA2_v3(`(>)`)(gcd(80), gcd(50))
valleapYear2: Int=> Boolean=
liftA2_v2(`(>)`)(gcd(80), gcd(50))
defliftA2_v2[A,B,C,F[_]: Applicative](f: A => B => C)(fa: F[A], fb: F[B]): F[C] =
f `<$>` fa <*> fb
defliftA2_v3[A,B,C,F[_]: Applicative](f: A => B => C)(fa: F[A], fb: F[B]): F[C] =
f.pure <*> fa <*> fb
import scala.math.BigInt.int2bigInt
That’s all. I hope you found it useful.
If you would like a more comprehensive introduction to the Function Applicative, consider checking out the following deck.
https://fpilluminated.com/
If you would like a more comprehensive introduction to the Function Applicative, consider checking out the following deck.
https://fpilluminated.com/
Categories
TechnologyDownload
Download Slideshow Get the original presentation fileQuick Actions
Statistics
- Views 61
- Slides 25
- Age 476 days
Related Slideshows
11
8-top-ai-courses-for-customer-support-representatives-in-2025.pptx
JeroenErne2
48 views
10
7-essential-ai-courses-for-call-center-supervisors-in-2025.pptx
JeroenErne2
47 views
13
25-essential-ai-courses-for-user-support-specialists-in-2025.pptx
JeroenErne2
37 views
11
8-essential-ai-courses-for-insurance-customer-service-representatives-in-2025.pptx
JeroenErne2
34 views
21
Know for Certain
DaveSinNM
22 views
17
PPT OPD LES 3ertt4t4tqqqe23e3e3rq2qq232.pptx
novasedanayoga46
26 views