We actually had a conversation about this topic in the Haskell-Beginners channel of the FP Slack *today* (same day as you posted this, funny coincidence). It's covered pretty well in the book Haskell Programming From First Principles (Moronuki / Allen). Applicatives do indeed have a monoid "aspect" and a functor "aspect" to them; for a given `instance Applicative Sometype where`, the `Sometype a` has an explicit functor instance (where `a` is mapped) but also an implicit Monoid quality (where `Sometypes` are combined & have an identity). Some examples: For the list [] applicative, which I will alias as List: pure :: a -> List a - the implementation is to put a into a singleton list, `[a]`. A list of one element is the identity for the monoid of cartesian list product, because (a list of 1 el) * (a list of n els) is (a list of n els). () :: List (a -> b) -> List a -> List b - the implementation is cartesian product of lists, with each function applied to each value. The List of funcs is combined with the List of inputs to form a single output List. Followup on that one: there's an alternative applicative for lists, which is the ZipList. In the ZipList, the list combination logic is zipping, and the identity is not a singleton list but rather an infinitely-repeating list! A singleton list couldn't be the correct identity for a ZipList because it biases the resulting structure. If you zip a list of length 1 with any other list, you get a list of length 1. But if you zip a list of infinite length against another list of length n, you get a list of length n. For the Maybe applicative: pure :: a -> Maybe a - the implementation is to use Just, which is the identity for the monoid of Maybes. () :: Maybe (a -> b) -> Maybe a -> Maybe b - the implementation is to use short-circuiting, exactly analagous to the `All` monoid for booleans. If you ever have a Nothing, the result is Nothing. If *all* values are Just, you combine them to also produce a Just. So in general, the "structure" or "context" of the applicative has to have logic for combining two structures into one, and an identity element that doesn't bias the structure in any way; that's the Monoid part. Whereas the values inside the context have to be mappable/transformable, à la Functor.
Extremely awesome video. I really hope you do more videos like this!! Really shows off refactoring in Haskell. There's an even deeper relationship between Applicative and Monoid; compare mempty with pure and mappend with
Tsoding Yes. You have normal function application ($) :: (a -> b) -> a -> b, at the bottom level, and monoid appending () :: f -> f -> f, at the higher level. And they combine to form (). In this perspetive, the only difference between applicatives and monads is that monads allow for interference between these two layers, where applicatives don't. I.e. the value 'a' can be used to influence which monoid 'f' gets appended at the higher level. I only realized this recently too and it blew my mind.
One more thing, if you want to use indices which aren't bounded (Integer, Float, Double, Rational... are a few examples of such types), "Min a" won't be a Monoid, since that requires "Bounded a". To accommodate that, you can wrap those types in an extra "Maybe", since there's an instance "Semigroup a => Monoid (Maybe a)" (since base-4.11.0.0). Another thing worth noting is that you might also consider indexing your source by line and column number, which can be sorted in lexicographical order (so (a, b) > (c, d) iff a > c or (a = c and b > d) ). It is also usually worth making a record type for your tokens with self-documenting accessor names.
You actually don't want to lex or tokenize into a [String] but rather into Either Error [Lexem] where e.g. type Lexem = (Token, Location) data Token = NumLiteral String | TextLiteral String | Identifier String | LeftParen | RightParen | ...
I hope I'm not carrying coals to Newcastle with this, but you can do even better and use Mabe's big sister, Either. The concepts are pretty much the same, but where you have Nothing in Maybe, you have Left in Either. This is by convention a place to encode failure (the success case goes into the Right instead of Some, as in "Right is right"). If you want to be really thorough about this, you could also design an ADT around the errors you'd expect so you could even pattern match over them.
IMO, in this case `NonEmpty (Indexed Char) -> Indexed [Char]` would be better than using `error`/`Maybe`/`Either`. The function simply cannot fail. Look up "Type safety back and forth" if you're interested
There is also a strong relationship between Monoid and Monad. Maybe you’ve heard the infamous “A monad is just a monoid in the category of endofunctors, what’s the problem?”. What this means is that a monad is a monoid with the multiplication set to “join” and identity element set to “pure” for any specific endofunctor (a functor that maps between some category C back to C itself). All functors defined using the Functor type class are endofunctors where the category C is the (pseudo-)category Hask. “Join” can be defined in terms of (>>=) and vice versa. join x = x >>= id. x >>= f = join (fmap f x) Hask can be thought of the category where the objects are types and the morphisms are Haskell functions on those types. Technically it is not really that due to laziness and bottom (undefined) but instead having something called CCPOs as objects allows for a more rigorous construction. Unfortunately, I don’t understand those objects so I can’t really go further into that explanation.
It is indeed Emacs. Here are a few links www.gnu.org/software/emacs/ ruclips.net/p/PLEoMzSkcN8oPH1au7H6B7bBJ4ZO7BXjSZ ruclips.net/video/PKaJoqQQoIA/видео.html ruclips.net/video/5p2Aq3bRuL0/видео.html
@@reo101 thank you very much for your kind answer Pavel. In the meantime I stumbled across his "how i configure my emacs" video by myself but at the time I left that question I wasn't aware that this video's author was Tsoder, because I have started watching this video before. So I'm sorry for the question. ^^ Thank you for the link. I have hears there is an Emacs "Vim-Mode Plugin", what do you think about this? Purists will of course despise it. Vim and Emacs. Eternal holy war, rite? Like between Ninjas and... fuk me. I have forgotten against whom. Ninjas vs. Jedi ? Does this have meme potential? Hardly. Mustve been sth else.
@@friedrichwilhelmhufnagel3577 I can't make myself relearn a core editing ideology (emacs' hiding everything behind modifiers instead of chords) so for the time used Emacs personally (not a preset, from scrath config) (time was around a month or two) i found Emacs to be unusable without proper vim support. The thing is that many other plugins strive to look like native emacs features and design their keybinds and such with that in mind. So when one want the continue with the "vim" experience they hit a wall unless the plugin creator (or somebody else) adds support for vim-like usage (be it a plugin setting or another plugin altogether). Since I wanted to use quite a lot of plugins this quickly becase a big issue. Since then I'vr switched to using NeoVim fulltime (2+ years now). The editor api scripting language are muuuuch nicer to tinker with (it's lua - if you want more types you can use `teal` and if you want it to be more lispy (like i do) you can use `fennel`. both of them compile to lua and neovim and happily use them). Vim has a lot of great interfaces that some plugins may rely on while others can redefine them - for instance, vim has the `vim.fn.input()` function (and others) for text prompts of any kind. Any plugin can use that for text input/selection. The default impl is pretty basic (everything in the modeline) but one could write a plugin (and many have already done so) that redefines these function to , let's say, bring up a pretty floating window for your text input/selection needs. So all in all I really recommend giving nvim a try.
Of course - if starting from scratch, one could (semi) easily use emacs the way it was supposed to be used (w/o vim emulation), but IMO one you touch vim you can't rrally use any other editing env. Doesn't mean you cannot not use vim but that you'll greatly benefit from vim emulations (or straigh up nvim proccesses running in deamon mode) for the big IDEs like VSCode (so bloated, its basically an IDE, fight me) or the JetBrains stack
We actually had a conversation about this topic in the Haskell-Beginners channel of the FP Slack *today* (same day as you posted this, funny coincidence). It's covered pretty well in the book Haskell Programming From First Principles (Moronuki / Allen). Applicatives do indeed have a monoid "aspect" and a functor "aspect" to them; for a given `instance Applicative Sometype where`, the `Sometype a` has an explicit functor instance (where `a` is mapped) but also an implicit Monoid quality (where `Sometypes` are combined & have an identity). Some examples:
For the list [] applicative, which I will alias as List:
pure :: a -> List a - the implementation is to put a into a singleton list, `[a]`. A list of one element is the identity for the monoid of cartesian list product, because (a list of 1 el) * (a list of n els) is (a list of n els).
() :: List (a -> b) -> List a -> List b - the implementation is cartesian product of lists, with each function applied to each value. The List of funcs is combined with the List of inputs to form a single output List.
Followup on that one: there's an alternative applicative for lists, which is the ZipList. In the ZipList, the list combination logic is zipping, and the identity is not a singleton list but rather an infinitely-repeating list! A singleton list couldn't be the correct identity for a ZipList because it biases the resulting structure. If you zip a list of length 1 with any other list, you get a list of length 1. But if you zip a list of infinite length against another list of length n, you get a list of length n.
For the Maybe applicative:
pure :: a -> Maybe a - the implementation is to use Just, which is the identity for the monoid of Maybes.
() :: Maybe (a -> b) -> Maybe a -> Maybe b - the implementation is to use short-circuiting, exactly analagous to the `All` monoid for booleans. If you ever have a Nothing, the result is Nothing. If *all* values are Just, you combine them to also produce a Just.
So in general, the "structure" or "context" of the applicative has to have logic for combining two structures into one, and an identity element that doesn't bias the structure in any way; that's the Monoid part. Whereas the values inside the context have to be mappable/transformable, à la Functor.
Extremely awesome video. I really hope you do more videos like this!! Really shows off refactoring in Haskell. There's an even deeper relationship between Applicative and Monoid; compare mempty with pure and mappend with
Oh, yeah! So Applicative is like a Monoid but parameterized with a type... Interesting!
Tsoding yeah, also Applicative laws and Monoid laws are very similar. They both have associativity and 2 identity laws.
Tsoding Yes. You have normal function application ($) :: (a -> b) -> a -> b, at the bottom level, and monoid appending () :: f -> f -> f, at the higher level. And they combine to form (). In this perspetive, the only difference between applicatives and monads is that monads allow for interference between these two layers, where applicatives don't. I.e. the value 'a' can be used to influence which monoid 'f' gets appended at the higher level. I only realized this recently too and it blew my mind.
@@BrianMcKennaPuffnfresh thank you for blowing my mind
type cinnabun lmao
One more thing, if you want to use indices which aren't bounded (Integer, Float, Double, Rational... are a few examples of such types), "Min a" won't be a Monoid, since that requires "Bounded a".
To accommodate that, you can wrap those types in an extra "Maybe", since there's an instance "Semigroup a => Monoid (Maybe a)" (since base-4.11.0.0). Another thing worth noting is that you might also consider indexing your source by line and column number, which can be sorted in lexicographical order (so (a, b) > (c, d) iff a > c or (a = c and b > d) ).
It is also usually worth making a record type for your tokens with self-documenting accessor names.
Wow, that's super interesting! The learning never stops with Haskell!
You actually don't want to lex or tokenize into a [String] but rather into Either Error [Lexem] where e.g.
type Lexem = (Token, Location)
data Token = NumLiteral String | TextLiteral String | Identifier String | LeftParen | RightParen | ...
These streams were so much fun.
At 3:12, where you edit the type of mkToken, my brain suddenly goes bonkers.
Hoping to see more of your discoveries soon. Great Video.
Thank you....
Very nice! Thanks for making the video.
This remind me of 'traverse' in Control.Lens
No don't throw errors. Return Maybes!
I hope I'm not carrying coals to Newcastle with this, but you can do even better and use Mabe's big sister, Either. The concepts are pretty much the same, but where you have Nothing in Maybe, you have Left in Either. This is by convention a place to encode failure (the success case goes into the Right instead of Some, as in "Right is right").
If you want to be really thorough about this, you could also design an ADT around the errors you'd expect so you could even pattern match over them.
IMO, in this case `NonEmpty (Indexed Char) -> Indexed [Char]` would be better than using `error`/`Maybe`/`Either`. The function simply cannot fail. Look up "Type safety back and forth" if you're interested
There is also a strong relationship between Monoid and Monad. Maybe you’ve heard the infamous “A monad is just a monoid in the category of endofunctors, what’s the problem?”.
What this means is that a monad is a monoid with the multiplication set to “join” and identity element set to “pure” for any specific endofunctor (a functor that maps between some category C back to C itself). All functors defined using the Functor type class are endofunctors where the category C is the (pseudo-)category Hask. “Join” can be defined in terms of (>>=) and vice versa. join x = x >>= id. x >>= f = join (fmap f x)
Hask can be thought of the category where the objects are types and the morphisms are Haskell functions on those types. Technically it is not really that due to laziness and bottom (undefined) but instead having something called CCPOs as objects allows for a more rigorous construction. Unfortunately, I don’t understand those objects so I can’t really go further into that explanation.
Hello Taoding, what is your editor if i may ask ? I heared Emacs, but it looks like vim ?? Best wishes
It is indeed Emacs. Here are a few links
www.gnu.org/software/emacs/
ruclips.net/p/PLEoMzSkcN8oPH1au7H6B7bBJ4ZO7BXjSZ
ruclips.net/video/PKaJoqQQoIA/видео.html
ruclips.net/video/5p2Aq3bRuL0/видео.html
@@reo101 thank you very much for your kind answer Pavel. In the meantime I stumbled across his "how i configure my emacs" video by myself but at the time I left that question I wasn't aware that this video's author was Tsoder, because I have started watching this video before. So I'm sorry for the question. ^^
Thank you for the link.
I have hears there is an Emacs "Vim-Mode Plugin", what do you think about this? Purists will of course despise it. Vim and Emacs. Eternal holy war, rite? Like between Ninjas and... fuk me. I have forgotten against whom. Ninjas vs. Jedi ? Does this have meme potential? Hardly. Mustve been sth else.
@@friedrichwilhelmhufnagel3577 I can't make myself relearn a core editing ideology (emacs' hiding everything behind modifiers instead of chords) so for the time used Emacs personally (not a preset, from scrath config) (time was around a month or two) i found Emacs to be unusable without proper vim support. The thing is that many other plugins strive to look like native emacs features and design their keybinds and such with that in mind. So when one want the continue with the "vim" experience they hit a wall unless the plugin creator (or somebody else) adds support for vim-like usage (be it a plugin setting or another plugin altogether). Since I wanted to use quite a lot of plugins this quickly becase a big issue. Since then I'vr switched to using NeoVim fulltime (2+ years now). The editor api scripting language are muuuuch nicer to tinker with (it's lua - if you want more types you can use `teal` and if you want it to be more lispy (like i do) you can use `fennel`. both of them compile to lua and neovim and happily use them). Vim has a lot of great interfaces that some plugins may rely on while others can redefine them - for instance, vim has the `vim.fn.input()` function (and others) for text prompts of any kind. Any plugin can use that for text input/selection. The default impl is pretty basic (everything in the modeline) but one could write a plugin (and many have already done so) that redefines these function to , let's say, bring up a pretty floating window for your text input/selection needs. So all in all I really recommend giving nvim a try.
Of course - if starting from scratch, one could (semi) easily use emacs the way it was supposed to be used (w/o vim emulation), but IMO one you touch vim you can't rrally use any other editing env. Doesn't mean you cannot not use vim but that you'll greatly benefit from vim emulations (or straigh up nvim proccesses running in deamon mode) for the big IDEs like VSCode (so bloated, its basically an IDE, fight me) or the JetBrains stack
@@reo101 No need to fight you haha ;)