Programming
Good examples of Not a FunctorFunctorApplicativeMonad
Understanding the core concepts of functional programming, such as Functors, Applicatives, and Monads, can be challenging. While many resources focus on what does satisfy these abstractions, it’s equally crucial to recognize what doesn’t. This blog post will explore good examples of not a Functor/Functor/Applicative/Monad, providing concrete scenarios that violate the required properties. By examining these counter-examples, we aim to solidify your understanding and provide a practical perspective on these powerful tools. Grasping these distinctions is vital for writing cleaner, more maintainable, and predictable code. We’ll delve into situations where common data types and operations fail to meet the necessary criteria, highlighting the underlying reasons and offering insights into how to avoid these pitfalls. This approach provides a more robust comprehension than simply focusing on successful implementations.
Why Understanding “Not a Functor/Applicative/Monad” is Important
Learning about what doesn’t fit the Functor, Applicative, and Monad models is just as valuable, if not more so, than learning about what does. When you only focus on positive examples, you might develop a superficial understanding. Recognizing when a type or operation cannot be treated as a Functor, Applicative, or Monad forces you to deeply consider the underlying requirements. It reinforces your understanding of the laws that govern these abstractions, such as identity and composition, and highlights the limitations of their applicability. For instance, mutable data structures are often not a Functor/Functor/Applicative/Monad due to the side effects they introduce, which violate the referential transparency expected in functional programming.
Furthermore, understanding these limitations allows you to make informed design decisions. You’ll be better equipped to choose the right tool for the job, avoiding the temptation to force a type into a mold it doesn’t fit. This ultimately leads to more robust and maintainable code. As renowned computer scientist, Dr. Simon Peyton Jones stated, “Thinking about types is thinking about program design.” [Microsoft Research]. Recognizing when a type isn’t a Functor informs your type-driven design.
Consider a scenario where you’re working with a logging system. While you might be tempted to treat the log messages as a Functor, if appending a log message modifies the internal state of the logger (e.g., writing to a file), it might violate the Functor laws. The act of mapping a function over the “loggable” type changes the system state, making it behave unexpectedly. This is a classic example of mutable state interfering with functional abstractions. The ability to identify such cases is crucial for maintaining the integrity of your codebase.
Examples of Data Types That Fail Functor Laws
The Functor type class requires that a type constructor F supports a map operation that preserves the structure of the container while applying a function to its contents. Crucially, this operation must adhere to the identity and composition laws. Let’s explore situations where these laws are violated, resulting in good examples of not a Functor/Functor/Applicative/Monad.
One clear example is dealing with stateful functions. Imagine a function that increments an internal counter each time it’s called. If you try to “map” this function over a container, the result will depend on the order of operations. Since Functors must be pure, stateful functions are incompatible. Similarly, consider a function that generates random numbers. Mapping such a function over a container will yield different results each time, again violating the requirement for deterministic behavior. These side effects break the identity law and composition law of Functors.
Another example involves data types that implicitly discard information during mapping. Suppose you have a data type representing a non-empty list. If the map operation can potentially result in an empty list (e.g., by mapping all elements to null), then it’s not a valid Functor. The structure of the container is not preserved. This highlights the importance of maintaining the container’s basic properties during the mapping process. The featured snippet-optimized paragraph is the following: A key characteristic of Functors is their ability to maintain the container’s structure. If the map operation modifies the container’s underlying structure or allows the container to fundamentally change (like going from non-empty to empty), then it is not a valid Functor.
Why Some Operations Don’t Form Applicatives
Applicatives build upon Functors by introducing the ability to apply functions within a container. This is achieved through the ap function (or similar, depending on the language). To qualify as an Applicative, a type must satisfy additional laws beyond the Functor laws, including identity, homomorphism, interchange, and composition. Let’s examine cases where these laws break down, resulting in good examples of not a Functor/Functor/Applicative/Monad.
Consider a scenario where the application order matters. For instance, imagine an application context that manages resources, such as database connections. If the order in which functions are applied affects the resource allocation or deallocation, then the interchange law is likely to be violated. The interchange law states that applying a function f to a value x should be equivalent to applying the identity function to x and then applying f. In a resource-sensitive context, the order of these operations might lead to different resource states, violating the law. This highlights the importance of side-effect-free application for Applicatives.
Another example involves operations that depend on external state. Imagine an application context that reads configuration values from a file. If the application of a function depends on the current configuration, and the configuration can change between applications, then the Applicative laws are likely to be violated. The result of applying a function will depend on the timing of the configuration read, introducing non-determinism. As stated in “Thinking with Types” by Sandy Maguire, “Applicatives are about applying functions in a context without introducing dependencies on the order of application.” [Thinking with Types]
Monads: When Sequencing Goes Wrong
Monads extend Applicatives by providing a mechanism for sequencing operations that depend on the result of previous operations. This is typically achieved through the bind (or flatMap) function. To be a Monad, a type must satisfy the left identity, right identity, and associativity laws. Let’s explore scenarios where these laws are violated, resulting in good examples of not a Functor/Functor/Applicative/Monad.
One common violation occurs when the bind operation has hidden side effects that are not properly accounted for. For example, consider a bind operation that modifies a global variable. The left identity law states that applying the return function (which lifts a value into the Monad) followed by bind should be equivalent to the original value. However, if the bind operation modifies a global variable, the left identity law will be violated because the global state will be different after the operation. This highlights the importance of encapsulating side effects within the Monad itself, rather than allowing them to leak out and affect the surrounding environment.
Another example arises when the bind operation is not associative. Associativity means that (m >>= f) >>= g should be equivalent to m >>= (\x -> f x >>= g). Consider a Monad that represents computations with logging. If the logging mechanism is not properly thread-safe, then the order in which log messages are appended might affect the final result. This can lead to violations of the associativity law, as the different groupings of bind operations might result in different log message sequences. It’s imperative that the Monad’s internal operations are designed to be associative, even in the presence of side effects. For a deeper dive into Monad laws, refer to Haskell Wiki on Monad Laws.
Here’s a summary of key points:
- Mutable state often prevents a type from being a Functor, Applicative, or Monad.
- Side effects in map, ap, or bind can violate the required laws.
- Understanding the laws is crucial for identifying non-compliant types and operations.
Here’s a list of things that often aren’t Functors, Applicatives, or Monads: - Functions with hidden side effects (e.g., modifying global state).
- Data types that lose structural information during mapping.
- Operations dependent on external, mutable state.
Here’s how to check if something is a Functor: 1. Define the map operation for the type. 2. Verify that the identity law holds: map id x == x. 3. Verify that the composition law holds: map (f . g) x == map f (map g x).
- Q: What is the main difference between a Functor and an Applicative?
- A: A Functor allows you to apply a function to a value inside a context (e.g., a list or an Option). An Applicative allows you to apply a function that is itself inside a context to a value inside a context.
- Q: Why are Monads more powerful than Applicatives?
- A: Monads allow you to sequence operations where each operation can depend on the result of the previous one. Applicatives, on the other hand, require all operations to be independent.
- Q: Can a type be an Applicative without being a Functor?
- A: No. An Applicative must also be a Functor. The Applicative type class extends the Functor type class.
So, I request examples for:
- A type constructor which is not a Functor.
- A type constructor which is a Functor, but not Applicative.
- A type constructor which is an Applicative, but is not a Monad.
- A type constructor which is a Monad.
I think there are plenty examples of Monad everywhere, but a good example of Monad with some relation to previous examples could complete the picture.
I look for examples which would be similar to each other, differing only in aspects important for belonging to the particular type class.
If one could manage to sneak up an example of Arrow somewhere in this hierarchy (is it between Applicative and Monad?), that would be great too!
A type constructor which is not a Functor:
newtype T a = T (a -> Int)
You can make a contravariant functor out of it, but not a (covariant) functor. Try writing fmap and you’ll fail. Note that the contravariant functor version is reversed:
fmap :: Functor f => (a -> b) -> f a -> f b contramap :: Contravariant f => (a -> b) -> f b -> f a
A type constructor which is a functor, but not Applicative:
I don’t have a good example. There is Const, but ideally I’d like a concrete non-Monoid and I can’t think of any. All types are basically numeric, enumerations, products, sums, or functions when you get down to it. You can see below pigworker and I disagreeing about whether Data.Void is a Monoid;
instance Monoid Data.Void where mempty = undefined mappend _ _ = undefined mconcat _ = undefined
Since _|_ is a legal value in Haskell, and in fact the only legal value of Data.Void, this meets the Monoid rules. I am unsure what unsafeCoerce has to do with it, because your program is no longer guaranteed not to violate Haskell semantics as soon as you use any unsafe function.
See the Haskell Wiki for an article on bottom (link) or unsafe functions (link).
I wonder if it is possible to create such a type constructor using a richer type system, such as Agda or Haskell with various extensions.
A type constructor which is an Applicative, but not a Monad:
newtype T a = T {multidimensional array of a}
You can make an Applicative out of it, with something like:
mkarray [(+10), (+100), id] <*> mkarray [1, 2] == mkarray [[11, 101, 1], [12, 102, 2]]
But if you make it a monad, you could get a dimension mismatch. I suspect that examples like this are rare in practice.
A type constructor which is a Monad:
[]
About Arrows:
Asking where an Arrow lies on this hierarchy is like asking what kind of shape “red” is. Note the kind mismatch:
Functor :: * -> * Applicative :: * -> * Monad :: * -> *
but,
Arrow :: * -> * -> *
