Menu
According to 'Learn you a Haskell', the implementation of <*> for lists is:
fs <*> xs = [f x | f <- fs, x <- xs]
Am I mistaken, or is this sugared monadic code based on >>= ?
As far as I understand, it should be possible to implement <*> only using fmap, as it is the case with applicative Maybe.
How could <*> for lists be implemented only using fmap? (and possibly without concat-ing things?)
BTW, a few pages later I see the same issue with regards to the implementation of <*> for applicative IO.
823
runState is defined as a function that takes a single argument. And it returns a function that takes a single argument, to which we can then apply an initial state value.
Haskell is a pure language Moreover, Haskell functions can't have side effects, which means that they can't effect any changes to the "real world", like changing files, writing to the screen, printing, sending data over the network, and so on.
The I/O monad contains primitives which build composite actions, a process similar to joining statements in sequential order using `;' in other languages. Thus the monad serves as the glue which binds together the actions in a program.
One thing I noticed was that Tuple does not have a Monad instance. Which already extremely heavily restricts what we can make the Monad instance be.
No, this is not sugared monadic code based on >>=. If it were, the definition of >>= in the Monad [] instance would be circular.
instance Monad [] where
{-# INLINE (>>=) #-}
xs >>= f = [y | x <- xs, y <- f x]
...
The list comprehensions are syntactic sugar for let, if, and concatMap. From the Haskell Report:
[ e | b, Q ] = if b then [ e | Q ] else [] [ e | let decls, Q ] = let decls in [ e | Q ] [ e | p <- l, Q ] = let ok p = [ e | Q ] ok _ = [] in concatMap ok l
The Monad [] instance is easy to define in terms of concatMap, but concatMap was defined in GHC.List (and is now possibly defined in Data.Foldable). Neither GHC.List nor Data.Foldable is imported into GHC.Base, so defining the Monad instance for lists in GHC.Base in terms of concatMap is impossible:
instance Monad [] where
(>>=) = flip concatMap -- concatMap isn't imported
Defining these instances in terms of list comprehension gets around needing to import the module containing concatMap to reuse it defining >>=.
In GHC there are two implementations of list comprehensions. One rewrites them in terms of the GHC.Base build and foldr similar to the Data.Foldable concatMap. The other implementation generates recursive functions in place of concatMap as described by Wadler.
196
There are lots of cases where the Applicative instance is satisfied by monadic functions, I've seen
instance Applicative MyMonadThatIsAlreadyDefined where
pure = return
(<*>) = ap
Also, <*> can't be written using only fmap, at least not in general. That's the point of <*>. Try writing <*> in terms of just fmap, I'll be very surprised if you manage it (in such a way that is well behaved and follows the applicative laws). Remember that the chain is
Functor > Applicative > Monad
Where > can be thought of as superset. This is saying that the set of all functors contains the set of all applicatives, which contains the set of all monads. If you have a monad, then you have all the tools needed to use it as an applicative and as a functor. There are types that are functorial but not applicative, and types that are applicative by not monadic. I see no problem in defining the applicative instance in this manner.
43
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
