Derivation involving (->) applicative instance

gistfile1.txt

lift2 :: (Applicative f) = > (a -> b -> c) -> f a -> f b -> f c

----------

(\a -> State (\s -> (p a s, S.insert a s))) 

=> Split up s function into component-wise functions [Definition of lift2 for (->)]
   lift2 :: (a -> b -> c) -> (s -> a) -> (s -> b) -> (s -> c)
   lift2 :: (a -> b -> (a, b)) -> (s -> a) -> (s -> b) -> (s -> (a, b))

\a -> State (lift2 (\a1 a1 -> (a1, a2)) (\s -> p a s) (\s -> S.insert a s))

=> [Eta Reduction]

\a -> State (lift2 (,) (p a) (S.insert a))

=> Factor out the inside a and apply a [Beta Abstraction]

\a -> State ((\b -> lift (,) (p b) (S.insert b)) a)

=> Split up b function into component-wise functions [Definition of lift2 for (->)]
   lift2 :: (a -> b -> c) -> (s -> a) -> (s -> b) -> (s -> c)

\a -> State ((lift2 (\a1 a2 -> lift (,) a1 a2) (\b -> p b) (\b -> S.insert b)) a)

=> [Eta Reduction]

\a -> State ((lift2 (lift (,)) p S.insert) a)

=> [Eta Reduction]

State . (lift2 (lift (,)) p S.insert)