7 ms·

This misses the more simple explanation of Monads: They're functions provided by the language core, that cannot be implemented in the language itself,

• FreezerburnV 13y ago
  Can you give an example of a language rule which a Monad might implement? I sort of understand what you mean, but an example would help me (and maybe others?) form a more concrete understanding. And if at all possible, don't use Haskell being unable to mutate state as an example. Maybe an example for Javascript or Python?
  • danidiaz 13y ago
    Nullable types in C# "The predefined unary and binary operators and any user-defined operators that exist for value types may also be used by nullable types. These operators produce a null value if the operands are null; otherwise, the operator uses the contained value to calculate the result." http://msdn.microsoft.com/en-us/library/2cf62fcy.aspx http://msdn.microsoft.com/en-us/library/2cf62fcy.aspx They are useful to avoid repeated null checking. This can be modeled as a Monad with a notion of "failure". In Haskell that would be the Maybe monad. You would have to "lift" the arithmetic functions into it and work with "Maybe Int" values instead of "Int" values. An if we swapped the Maybe monad with the List (nondeterminism) monad, we could work with list of values and obtain a list of results for all possible combinations (instead of just one result or failure.)
  • tel 13y ago
    Here's an interesting one: let's implement backtracking non-deterministic parsing as a Monad. If the code below is complex remember that it really is a near complete implementation of a backtracking non-deterministic parser from scratch using no libraries. We'll do it first without any mention of the M-word. A parser is the kind of thing that consumes a string and returns a parsed value along with some "leftover" string data. For instance, a digit parser would look like (in Haskell types) digitParse :: String -> (Int, String) digitParse ('1' : leftover) = (1, leftover) digitParse ('2' : leftover) = (2, leftover) digitParse ('3' : leftover) = (3, leftover) ... We can begin here and incrementally add more features. For instance, what happens when digitParse is applied to "foo". It ought to fail! To solve this, we'll introduce the Maybe (or Option) type digitParse :: String -> Maybe (Int, String) digitParse ('1' : leftover) = Just (1, leftover) ... digitParse ('f' : leftover) = Nothing ... Finally, if we have a parser which is sensitive to both apples and apricots then we might want to augment our return type with a notion of multiplicity of successes. We'll use a list for this and I want to note specially that we can now get rid of the notion of failure as represented by Maybe because we can use use the empty list ([]) to mean "parse failure". All together we can call this type a Parser. A Parser which attempts to parse a polymorphic type can be considered as well, so we'll leave that as a type variable newtype Parser a = Parser (String -> [(a, String)]) runParser :: Parser a -> String -> [(a, String)] runParser (Parser f) = f Now we can update the previous type `digitParse` digitParse :: Parser Int --- All by itself, Parsers aren't useful. We need to be able to combine them to make sense of a larger string. For instance, let's use the original notion of digitParser to build twoDigitParser twoDigitParser :: String -> ((Int, Int), String) twoDigitParser input = let (i1, leftover1) = digitParser input (i2, leftover2) = digitParser leftover1 in ( (i1, i2), leftover2 ) Not too bad. We could even use recursion to parse a whole list of digits. manyDigitParser :: String -> ([Int], String) manyDigitParser input = let (i, leftover) = digitParser input (is, leftover') = manyDigitParser leftover in ( i : is, leftover' ) To make this truly work we'd want to layer in the notions of failure and non-determinism afforded by the Maybe type and the list type, but this simple example should suggest that writing all of this stuff out would be a LOT of boilerplate. We'd like to build up to using monads to reduce all of that boilerplate. Ultimately we'll be able to define the fully non-deterministic `manyDigitParser` as manyDigitParser :: Parser [Int] manyDigitParser = do i <- digitParser is <- manyDigitParser return (i : is) Or even manyDigitParser :: Parser [Int] manyDigitParser = liftM2 (:) digitParser manyDigitParser --- Monads depend on Functors, so we'll begin there. Functor just means that if we have a type Parser ty1 we can transform it into a type Parser ty2. For instance, let's say I have a function that converts lists of Int to a single Int by gluing digits together. glueDigits :: [Int] -> Int A Functor over Parser would let me turn manyDigitParser into integerParser integerParser :: Parser Int integerParser = fmap glueDigits manyDigitParser To write it we need to define fmap polymorphically to just reach in modify the return type of our Parser. We'll destruct and reconstruct a Parser type to do this. instance Functor Parser where fmap modify (Parser parse) = Parser (\input -> let results = parse f in map (\(return, leftover) -> (modify return, leftover)) results ) Now `integerParser` is perfectly valid code and Parser is an instance of Functor. > :type fmap (+1) (undefined :: Parser Int) fmap (+1) (undefined :: Parser Int) :: Parser Int > :type fmap (\_ -> 3) (undefined :: Parser Char) fmap (\_ -> 3) (undefined :: Parser Char) :: Parser Int --- Now we get to the meat of things. We'll define a notion of Applicative, another superclass of Monad. Applicative just says two things-- 1. We ought to be able to make a constant parser--one which always succeeds, always returns some constant value, and doesn't consume any input constantParser :: a -> Parser a constantParser a = Parser (\string -> [(a, String)]) 2. We ought to be able to take a parser which returns a function and apply it to a parser which returns an input to that function as if they were regular values. We'll do so by running the function parser first and then the value parser and combining their results. In types that looks like apParser :: Parser (a -> b) -> Parser a -> Parser b apParser (Parser fparse) (Parser aparse) = Parser (\input -> [ (fun aval, aleftovers) | (aval, aleftovers) <- aparse fleftovers , (fun, fleftovers) <- fparse input ] ) The above syntax is just a list comprehension exactly like Python's. We use these two functions to form another typeclass instance for Applicative and reveal the generic names of constantParser and apParser instance Applicative Parser where pure = constantParser (<*>) = apParser --- Finally, we can move to the brunt of the problem: the Monad instance. Again, the entire goal here is just to abstract out the methods of sequencing parsers that we did manually at the very beginning. We'll do it first for the basic parser type. newtype BasicParser a = BasicParser (String -> (a, String)) Monadic sequencing is a little strange to grasp at first. Like Applicative we need a way to inject constants into BasicParser. instance Monad BasicParser where return a = BasicParser (\input -> (a, input)) ... But we also need to somehow consolidate those lets from above. To do this we'll write a function called bind (but written (>>=)) that has the type (BasicParser a -> (a -> BasicParser b) -> BasicParser b). BasicParser parser >>= continuation = BasicParser (\input -> let (a, leftovers1) = parser input (b, leftovers2) = runParser (continuation a) leftovers1 in (b, leftovers2) ) Notice how we had to use that exact same let construct to define the parser? That's why it gets abstracted away. We can do the same for the more general non-deterministic, failing parser instance Monad Parser where return = pure Parser parser >>= continuation = Parser (\input -> [ (b, leftover2) , (b, leftover2) <- runParser (continuation a) leftover1 , (a, leftover1) <- parser input ] ) --- So while that's a fairly large amount of abstract code, the end result is that we've embedded a fairly complex effect into our language—one that no reasonable language would have built in for you---non-determistic backtracking parsing. We can also centralize our optimizations of that parser into the monadic code and reap the benefits across the entire codebase. Furthermore, most of what I wrote above, while abstract, requires almost no creativity as it just comes from recognizing that our Parser monad is a certain, standard combination of the State and List monads.
    • FreezerburnV 13y ago
      Wow. I have to say, at least on a cursory reading, this might be one of the best descriptions of what a Monad is. I feel like I understand them a little bit more just from going over what you wrote quickly. I'm going to go over this with a fine tooth comb when I have a little more time to do so. (was eating some lunch at work, and I don't know Haskell syntax very well, so while I picked up some gists of what you meant, I need to actually take the time to parse what the syntax means) Thank you so much for taking the time to write this all out. This kind of answer is one of the reasons I still read HN comments :)
      • tel 13y ago
        I'm glad! I was a bit worried it was a lot of code all at once, but Monads are best grasped by lots of examples that flex the API instead of talking about them in the abstract. Feel free to email me if you have further questions. (And I'm halfway tempted to write my own "Oi, fine, here's what a monad is" post soon enough. They're really not that strange, but it's easy to get things confused.)
  • Mithaldu 13y ago
    In Haskell some big rules you get around are: 1. Functional purity must be maintained for all code. This means for example that no side effects (IO) may happen. Thus some monads exist for the simple purpose of doing IO. 2. As you mentioned, state may not be mutated. To circumvent that there's a monad that simply marks a code block as "variables of this type may be changed in here, as long as they don't get out of this scope". 3. I only know about this vaguely, but as i understand it Haskell is strictly typed. This makes some things inconvenient, so Maybe allows some loose typing. I can't give examples in JS, but i actually got one for python: Decorators. In Python you cannot implement a function with this specification: It takes exactly these inputs in this order: 1) a function object, 2) a function name, 3) a multiline anonymous function. It calls the function passed as the first parameter, with the third parameter as its parameter. It takes the result, which is expected to be a function, and installs it in its calling scope as a new function, with the name passed in the second parameter. Since this is not possible to implement in pure python, decorators were implemented in the core. I'm not 100% sure, but i think they actually do qualify as monads.
    • dllthomas 13y ago
      For the record, Data.Dynamic has a type called Dynamic which can be used to weaken typing. It's not a monad, though - it only implements Show and Typeable (and recently Exception, apparently). http://hackage.haskell.org/package/base-4.6.0.1/docs/Data-Dynamic.html#t%3ADynamic http://hackage.haskell.org/package/base-4.6.0.1/docs/Data-Dy...
    • tel 13y ago
      1. IO doesn't have to be a monad, it simply was designed that way because the monad interface is so nice. In older (very functional) versions of Haskell this wasn't the case. 2. That's honestly not a bad description of the State monad spoken using procedural vocabular, but it is very far away from an accurate representation. At the very least it's worth noting that this isn't a syntactic thing—all of the elements are first-class. 3. Maybe is still strictly typed. It causes the possibility of null to be represented at the type level so that nobody ever accidentally forgets to check it. I never get null errors in Haskell. Finally, decorators are Functors perhaps, if you strain to look at them that way, but not at all monads.
  • GeneralMayhem 13y ago
    The point where a JS developer is most likely to run into monads is with asynchronous code. We call it "callback hell," and the reason it exists is because async callbacks, like monads, can't be easily "escaped" - everything done with a result must be used in the same monadic (asynchronous) context. Once you enter a callback-based function, you usually can't simply return from it and go back to standard sequentially-executed code. It takes a bit more work to formally show that continuations follow the monad laws, but that's as much as it took for me to begin to get the concept.
• saryant 13y ago
  I'm not sure about that. Scala's Option monad is just a class in the standard library, not a language feature. http://www.scala-lang.org/api/current/index.html#scala.Option http://www.scala-lang.org/api/current/index.html#scala.Optio...
  • Mithaldu 13y ago
    I'll be honest, i have no idea what any of the stuff written on that page means. Can you show me the implementation of that class in pure Scala code?
    • saryant 13y ago
      Here's the implementation: https://github.com/scala/scala/blob/v2.10.3/src/library/scala/Option.scala#L1 https://github.com/scala/scala/blob/v2.10.3/src/library/scal... (FYI, many Scaladocs have links back to the code on Github)
      • Mithaldu 13y ago
        Alright, so it really is just a Scala class with some handy shortcuts. Please do note though that the docs you linked do not think it is a monad, just that it's easy to think of it as one. Edit: In fact, it kinda smells like how Perl works when you do this: no warnings 'undefined';
        • frowaway001 13y ago
          > Please do note though that the docs you linked do not think it is a monad, just that it's easy to think of it as one. Heh?
• tel 13y ago
  Excepting that your explanation is not at all true. Even if you have mutable state you might want to use the State monad to implement it. Even if you have continuations you might want to use the Cont monad to implement it. No language has Parser built into the language itself—it's really just an invention available when you start to reify contexts as datatypes. Monad is about abstracting over a common pattern of sequencing side effects. These can be available in the language or not. Once you reflect that sequencing into a monad then it often becomes reified in such a way that makes side effects easier to track and understand.
  • Mithaldu 13y ago
    > Even if you have mutable state you might want to use the State monad to implement it. Why? If you can just write whatever you need in the language purely itself, why would you want to do that. Please be detailed and try to keep your dictionary simple. Using words like "reified" doesn't really help anyone to understand what you're trying to say, when it's known and accepted that the topic is very complicated.
    • dllthomas 13y ago
      What've you got against "reified"?
    • tel 13y ago
      (1) Backtracking is easy with the state monad since you can snapshot your entire "world" without trouble and replay it as needed. (2) Monads cause you to tag your types with effects that they are using. This means that your code is self-documenting about the side-effects it performs. In non-pure languages you still have to trust that the code isn't breaking convention, but it's a very powerful documentation methodology. (3) Creation of arbitrarily complex effects via stacking. While your language might have state and even non-determinism, it probably doesn't have their combination built-in. Their combination forms a very nice backtracking, non-deterministic parser almost automatically (see a loonnngg comment of mine elsewhere in this thread). (4) Optimization and compilation. While not directly possible with vanilla State, once you begin to use monads to represent effects it's easy to go back through and optimize your entire "language" by optimizing your monad implementations. You can even optimize them right into other targets like the Accelerate library which cross-compiles certain fragments of your Haskell—which look like mostly garden-variety normal Haskell—into GPU code.
• samstokes 13y ago
  I assume that definition is motivated by the Haskell IO monad, but it's unfortunately inaccurate. Haskell IO is provided by the language core, but that's not what makes it a monad - in older versions of Haskell IO was not monadic, but the language still provided IO operations. Monad is just an interface that the IO type supports, which allows you to structure your code in a particular way (an imperative-looking sequence of instructions and assignments) that people find more intuitive and convenient. You can still use IO without using the monadic interface (e.g. it's also a Functor). Conversely, most other Haskell monads are implemented in pure Haskell and are fairly easy to reimplement yourself. The State monad in the standard library is pure Haskell code.
  • Mithaldu 13y ago
    How does a complete Haskell program using non-monadic IO look like? As for "most other Haskell monads", from what i can tell they're just wrappers around the core monads with additional functionality tacked on and i consider it lazy to also call them monads instead of wrappers.
    • dllthomas 13y ago
      Most monads for which you can implement a monad transformer are implemented by wrapping the monad transformer around Identity, but that's simply because you would otherwise be implementing basically the same thing twice. My impression has been that they were originally implemented directly and only transformer-ified later. Certainly, there is no reason that couldn't have been done. Identity doesn't involve any particular voodoo: newtype Identity a = Identity { runIdentity :: a } instance Monad Identity where return a = Identity a m >>= k = k (runIdentity m) Haskell originally didn't include monadic IO - it was introduced in version 1.3, IIRC. IO looked like lazy streams of events, but it was pretty messy and pretty possible to deadlock, from what I hear. Writing modern Haskell, doing IO without any use of the IO type isn't possible, but you can - in principle - avoid ever using the fact that it's a monad by simply calling unsafePerformIO immediately on any IO action. Good luck actually ordering your IO operations, though.
    • danidiaz 13y ago
• duaneb 13y ago
  Monads are easy to implement in pretty much any language—are you referring to the `do` syntax?
• danidiaz 13y ago
  In Haskell, only the IO monad (and perhaps ST as well) is tied to the language's "core". All other monads are conventional Haskell code. It's better to think of them as a sort of design pattern.
  • Mithaldu 13y ago
    Since you said the same thing as someone else, please see: https://news.ycombinator.com/item?id=7076738 https://news.ycombinator.com/item?id=7076738