https://wiki.haskell.org/api.php?action=feedcontributions&user=Benmachine&feedformat=atomHaskellWiki - User contributions [en]2020-01-23T20:07:24ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=User:Benmachine&diff=63171User:Benmachine2019-12-15T14:45:54Z<p>Benmachine: </p>
<hr />
<div>== Contributions ==<br />
<br />
Articles written mostly by me, in descending order of how much I like them:<br />
<br />
* [https://wiki.haskell.org/index.php?title=Non-strict_semantics&oldid=63164 Non-strict semantics]<br />
* [https://wiki.haskell.org/index.php?title=Pure&oldid=56834 Pure]<br />
* [https://wiki.haskell.org/index.php?title=Polymorphism&oldid=59216 Polymorphism]<br />
* [https://wiki.haskell.org/index.php?title=Seq&oldid=59016 seq]<br />
* [https://wiki.haskell.org/index.php?title=Impredicative_types&direction=next&oldid=55281 Impredicative types]<br />
* [https://wiki.haskell.org/index.php?title=Newtype&oldid=36897 Newtype]<br />
* [https://wiki.haskell.org/index.php?title=Monoid&oldid=60323 Monoid]<br />
* [https://wiki.haskell.org/index.php?title=OCaml&oldid=55119 OCaml]<br />
<br />
== Opinions ==<br />
<br />
I have some objections to [[User:benmachine/Overqualified modules|module overqualification]]<br />
<br />
== Drafts ==<br />
<br />
[[User:benmachine/Cont|Cont tutorial]] (too much magic)<br />
<br />
[[User:benmachine/Newtype]] (not finished)</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine&diff=63170User:Benmachine2019-12-15T14:27:22Z<p>Benmachine: </p>
<hr />
<div>== Contributions ==<br />
<br />
Articles written mostly by me (linking to specific revisions, in case they are later rewritten):<br />
<br />
* [https://wiki.haskell.org/index.php?title=Newtype&oldid=36897 Newtype]<br />
* [https://wiki.haskell.org/index.php?title=Seq&oldid=59016 seq]<br />
* [https://wiki.haskell.org/index.php?title=Non-strict_semantics&oldid=63164 Non-strict semantics]<br />
* [https://wiki.haskell.org/index.php?title=Monoid&oldid=60323 Monoid]<br />
* [https://wiki.haskell.org/index.php?title=Impredicative_types&direction=next&oldid=55281 Impredicative types]<br />
* [https://wiki.haskell.org/index.php?title=Pure&oldid=56834 Pure]<br />
* [https://wiki.haskell.org/index.php?title=OCaml&oldid=55119 OCaml]<br />
* [https://wiki.haskell.org/index.php?title=Polymorphism&oldid=59216 Polymorphism]<br />
<br />
== Opinions ==<br />
<br />
I have some objections to [[User:benmachine/Overqualified modules|module overqualification]]<br />
<br />
== Drafts ==<br />
<br />
[[User:benmachine/Cont|Cont tutorial]] (too much magic)<br />
<br />
[[User:benmachine/Newtype]] (not finished)</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine/Newtype&diff=63169User:Benmachine/Newtype2019-12-15T14:07:31Z<p>Benmachine: Created page with "A '''newtype''' declaration creates a fresh type with the same representation as an existing ("underlying") type. The most common reasons they are used are: * providing addit..."</p>
<hr />
<div>A '''newtype''' declaration creates a fresh type with the same representation as an existing ("underlying") type. The most common reasons they are used are:<br />
<br />
* providing additional type safety, by making different uses of the same underlying type incompatible,<br />
* creating abstract data types,<br />
* permitting alternative or additional typeclass instances to be declared for the new type.<br />
<br />
== Syntax ==<br />
<br />
The syntax is similar to that of [[data]] declarations:<br />
<br />
<haskell><br />
-- name of the new type<br />
-- | name of its value constructor<br />
-- | | underlying type<br />
-- | | |<br />
-- v v v<br />
newtype Username = MkUsername String<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
-- may also have type parameters<br />
newtype Parser a = MkParser (String -> Maybe (String, a))<br />
<br />
-- or record syntax<br />
newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }<br />
</haskell><br />
<br />
Following the above declarations, we have new type constructors <hask>Username</hask>, <hask>Parser</hask>, and <hask>StateT</hask>, and new value constructors with the following types:<br />
<br />
<haskell><br />
MkUsername :: String -> Username<br />
MkParser :: (String -> Maybe (String, a)) -> Parser a<br />
<br />
StateT :: (s -> m (a, s)) -> StateT s m a<br />
runStateT :: StateT s m a -> (s -> m (a, s))<br />
</haskell><br />
<br />
Notice that in the case of StateT, the type constructor and the value constructor have the same name: some find that this is a helpful mnemonic, while others find it confusing, and insist on something like the <tt>Mk</tt> prefix used above (both these conventions also exist for single-constructor data declarations).<br />
<br />
By contrast to data declarations, which may have several value constructors, each with zero or more fields containing values of other types, newtypes may only have exactly one constructor, and that constructor must have exactly one field (which, as shown above, is permitted to be a record field). This ensures that the new type and the underlying type – the type of that single field of that single constructor – are in direct correspondence.<br />
<br />
== Uses ==<br />
<br />
So, if a newtype declaration can only create a type that's exactly the same as an existing type, why bother at all? Let's return to the three bullet points given at the start of the article:<br />
<br />
=== Additional type safety ===<br />
<br />
Sometimes you use one type for many different purposes, and it's important not to get them mixed up.</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine&diff=63168User:Benmachine2019-12-15T14:02:09Z<p>Benmachine: </p>
<hr />
<div>== Contributions ==<br />
<br />
I wrote a [[User:benmachine/Cont|Cont tutorial]] of sorts.<br />
<br />
I have some objections to [[User:benmachine/Overqualified modules|module overqualification]]<br />
<br />
== Drafts ==<br />
<br />
[[User:benmachine/Cont|Cont tutorial]] (too much magic)<br />
<br />
[[User:benmachine/Newtype]] (not finished)<br />
<br />
= Newtype =<br />
<br />
A '''newtype''' declaration creates a fresh type with the same representation as an existing ("underlying") type. The most common reasons they are used are:<br />
<br />
* providing additional type safety, by making different uses of the same underlying type incompatible,<br />
* creating abstract data types,<br />
* permitting alternative or additional typeclass instances to be declared for the new type.<br />
<br />
== Syntax ==<br />
<br />
The syntax is similar to that of [[data]] declarations:<br />
<br />
<haskell><br />
-- name of the new type<br />
-- | name of its value constructor<br />
-- | | underlying type<br />
-- | | |<br />
-- v v v<br />
newtype Username = MkUsername String<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
-- may also have type parameters<br />
newtype Parser a = MkParser (String -> Maybe (String, a))<br />
<br />
-- or record syntax<br />
newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }<br />
</haskell><br />
<br />
Following the above declarations, we have new type constructors <hask>Username</hask>, <hask>Parser</hask>, and <hask>StateT</hask>, and new value constructors with the following types:<br />
<br />
<haskell><br />
MkUsername :: String -> Username<br />
MkParser :: (String -> Maybe (String, a)) -> Parser a<br />
<br />
StateT :: (s -> m (a, s)) -> StateT s m a<br />
runStateT :: StateT s m a -> (s -> m (a, s))<br />
</haskell><br />
<br />
Notice that in the case of StateT, the type constructor and the value constructor have the same name: some find that this is a helpful mnemonic, while others find it confusing, and insist on something like the <tt>Mk</tt> prefix used above (both these conventions also exist for single-constructor data declarations).<br />
<br />
By contrast to data declarations, which may have several value constructors, each with zero or more fields containing values of other types, newtypes may only have exactly one constructor, and that constructor must have exactly one field (which, as shown above, is permitted to be a record field). This ensures that the new type and the underlying type – the type of that single field of that single constructor – are in direct correspondence.<br />
<br />
== Uses ==<br />
<br />
So, if a newtype declaration can only create a type that's exactly the same as an existing type, why bother at all? Let's return to the three bullet points given at the start of the article:<br />
<br />
=== Additional type safety ===<br />
<br />
Sometimes you use one type for many different purposes, and it's important not to get them mixed up.</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine&diff=63167User:Benmachine2019-12-15T14:00:57Z<p>Benmachine: </p>
<hr />
<div>I wrote a [[User:benmachine/Cont|Cont tutorial]] of sorts.<br />
<br />
I have some objections to [[User:benmachine/Overqualified modules|module overqualification]]<br />
<br />
Draft space:<br />
<br />
= Newtype =<br />
<br />
A '''newtype''' declaration creates a fresh type with the same representation as an existing ("underlying") type. The most common reasons they are used are:<br />
<br />
* providing additional type safety, by making different uses of the same underlying type incompatible,<br />
* creating abstract data types,<br />
* permitting alternative or additional typeclass instances to be declared for the new type.<br />
<br />
== Syntax ==<br />
<br />
The syntax is similar to that of [[data]] declarations:<br />
<br />
<haskell><br />
-- name of the new type<br />
-- | name of its value constructor<br />
-- | | underlying type<br />
-- | | |<br />
-- v v v<br />
newtype Username = MkUsername String<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
-- may also have type parameters<br />
newtype Parser a = MkParser (String -> Maybe (String, a))<br />
<br />
-- or record syntax<br />
newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }<br />
</haskell><br />
<br />
Following the above declarations, we have new type constructors <hask>Username</hask>, <hask>Parser</hask>, and <hask>StateT</hask>, and new value constructors with the following types:<br />
<br />
<haskell><br />
MkUsername :: String -> Username<br />
MkParser :: (String -> Maybe (String, a)) -> Parser a<br />
<br />
StateT :: (s -> m (a, s)) -> StateT s m a<br />
runStateT :: StateT s m a -> (s -> m (a, s))<br />
</haskell><br />
<br />
Notice that in the case of StateT, the type constructor and the value constructor have the same name: some find that this is a helpful mnemonic, while others find it confusing, and insist on something like the <tt>Mk</tt> prefix used above (both these conventions also exist for single-constructor data declarations).<br />
<br />
By contrast to data declarations, which may have several value constructors, each with zero or more fields containing values of other types, newtypes may only have exactly one constructor, and that constructor must have exactly one field (which, as shown above, is permitted to be a record field). This ensures that the new type and the underlying type – the type of that single field of that single constructor – are in direct correspondence.<br />
<br />
== Uses ==<br />
<br />
So, if a newtype declaration can only create a type that's exactly the same as an existing type, why bother at all? Let's return to the three bullet points given at the start of the article:<br />
<br />
=== Additional type safety ===<br />
<br />
Sometimes you use one type for many different purposes, and it's important not to get them mixed up.</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine&diff=63166User:Benmachine2019-12-15T14:00:23Z<p>Benmachine: </p>
<hr />
<div>I wrote a [[User:benmachine/Cont|Cont tutorial]] of sorts.<br />
<br />
I have some objections to [[User:benmachine/Overqualified modules|module overqualification]]<br />
<br />
I wrote an [[User:benmachine/uninstall.sh|uninstall script]] for things cabal installs.<br />
<br />
Draft space:<br />
<br />
= Newtype =<br />
<br />
A '''newtype''' declaration creates a fresh type with the same representation as an existing ("underlying") type. The most common reasons they are used are:<br />
<br />
* providing additional type safety, by making different uses of the same underlying type incompatible,<br />
* creating abstract data types,<br />
* permitting alternative or additional typeclass instances to be declared for the new type.<br />
<br />
== Syntax ==<br />
<br />
The syntax is similar to that of [[data]] declarations:<br />
<br />
<haskell><br />
-- name of the new type<br />
-- | name of its value constructor<br />
-- | | underlying type<br />
-- | | |<br />
-- v v v<br />
newtype Username = MkUsername String<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
-- may also have type parameters<br />
newtype Parser a = MkParser (String -> Maybe (String, a))<br />
<br />
-- or record syntax<br />
newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }<br />
</haskell><br />
<br />
Following the above declarations, we have new type constructors <hask>Username</hask>, <hask>Parser</hask>, and <hask>StateT</hask>, and new value constructors with the following types:<br />
<br />
<haskell><br />
MkUsername :: String -> Username<br />
MkParser :: (String -> Maybe (String, a)) -> Parser a<br />
<br />
StateT :: (s -> m (a, s)) -> StateT s m a<br />
runStateT :: StateT s m a -> (s -> m (a, s))<br />
</haskell><br />
<br />
Notice that in the case of StateT, the type constructor and the value constructor have the same name: some find that this is a helpful mnemonic, while others find it confusing, and insist on something like the <tt>Mk</tt> prefix used above (both these conventions also exist for single-constructor data declarations).<br />
<br />
By contrast to data declarations, which may have several value constructors, each with zero or more fields containing values of other types, newtypes may only have exactly one constructor, and that constructor must have exactly one field (which, as shown above, is permitted to be a record field). This ensures that the new type and the underlying type – the type of that single field of that single constructor – are in direct correspondence.<br />
<br />
== Uses ==<br />
<br />
So, if a newtype declaration can only create a type that's exactly the same as an existing type, why bother at all? Let's return to the three bullet points given at the start of the article:<br />
<br />
=== Additional type safety ===<br />
<br />
Sometimes you use one type for many different purposes, and it's important not to get them mixed up.</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine/hasktag_bug&diff=63165User:Benmachine/hasktag bug2019-12-15T13:58:30Z<p>Benmachine: fixed</p>
<hr />
<div>Looks like this was fixed!</div>Benmachinehttps://wiki.haskell.org/index.php?title=Non-strict_semantics&diff=63164Non-strict semantics2019-12-15T13:55:26Z<p>Benmachine: demote a section heading</p>
<hr />
<div>An expression language is said to have [[non-strict semantics]] if expressions can have a value even if some of their subexpressions do not. Haskell is one of the few modern languages to have non-strict semantics by default: nearly every other language has [[strict semantics]], in which if any subexpression fails to have a value, the whole expression fails with it.<br />
<br />
This is one of the most important features in Haskell: it is what allows programs to work with conceptually infinite data structures, and it is why people say that Haskell lets you write your own control structures. It's also one of the motivations behind Haskell being a [[pure]] language (though there are several other good ones).<br />
<br />
== What? ==<br />
<br />
Any sufficiently capable programming language is ''non-total'', which is to say you can write expressions that do not produce a value: common examples are an exception thrown, an infinite loop, or unproductive recursion, e.g. the following definition in Haskell:<br />
<br />
<haskell><br />
noreturn :: Integer -> Integer<br />
noreturn x = negate (noreturn x)<br />
</haskell><br />
<br />
or the following Python function:<br />
<br />
def noreturn(x):<br />
while True:<br />
x = -x<br />
<br />
return x # not reached<br />
<br />
both fail to produce a value when executed. We say that <tt>noreturn x</tt> is undefined, and write <tt>noreturn x = [[Bottom|⊥]]</tt>.<br />
<br />
In Python the following expression to check if <tt>2</tt> is in some list:<br />
<br />
2 in [2,4,noreturn(5)]<br />
<br />
also fails to have a value, because in order to construct the list, the interpreter tries to work out <tt>noreturn(5)</tt>, which of course doesn't return a value. This is called '''innermost-first''' evaluation: in order to call a function with some arguments, you first have to calculate what all the arguments are, starting from the innermost function call and working outwards. The result is that Python is ''strict'', in the sense that calling any function with an undefined argument produces an undefined value, i.e. <tt>f(⊥) = ⊥</tt>. If your language uses innermost-first evaluation, it correspondingly must have strict semantics.<br />
<br />
In Haskell, an analogous expression:<br />
<br />
<haskell><br />
elem 2 [2, 4, noreturn 5]<br />
</haskell><br />
<br />
in fact has the value <tt>True</tt>. The program does not have to compute <tt>noreturn 5</tt> because it is irrelevant to the overall value of the computation: only the values that are necessary to the result need be computed. This is called '''outermost-first''' evaluation because you first look at the outermost function call, <tt>elem</tt>, to see if it needs to use its arguments, and only if it does do you look at what those arguments are. This means that you can write a function that doesn't look at its argument, so it will return a value even if the argument is <tt>⊥</tt>. Such functions are ''not strict'', i.e. they satisfy <tt>f(⊥) ≠ ⊥</tt>. Practically, this means that Haskell functions need not completely compute their arguments before using them, which is why e.g. <tt>take 3 [1..]</tt> can produce <tt>[1,2,3]</tt> even though it is given a conceptually infinite list.<br />
<br />
Note that ''semantics'' is, pedantically speaking, just about which expressions have a value, and what the value is, not how you figure it out. Outermost-first evaluation is not the only way to have non-strict semantics: a speculative evaluation strategy, that evaluates arguments in parallel with the function in case they are needed later, could also be non-strict, as long as whenever the speculative evaluation failed, the evaluation of the function continued.<br />
<br />
Note also that according to the <tt>f(⊥) ≠ ⊥</tt> definition, lots of seemingly-nonstrict functions are actually strict, e.g. <tt>elem 2</tt> from the above example! However, strictness can be more nuanced than that: e.g. we can say that <tt>elem 2</tt> is non-strict in the part of the list following the first 2, so will return a non-⊥ answer to <tt>elem 2 (2 : ⊥)</tt>. We might say that a function is "strict in the spine of the list" (like <tt>length</tt>, which will ignore ⊥ in the elements of the list) or "strict in the second component of the tuple (like... <tt>snd</tt>, I guess).<br />
<br />
== Why? ==<br />
<br />
To correct a common misconception about non-strict semantics, it is not a performance feature. Non-strict semantics allows your language to only evaluate the things it needs to, but if you write your programs carefully, you'll only compute what is absolutely necessary ''anyway'', so the extra time your program spends working out what should and shouldn't be evaluated is time wasted. For this reason, a very well-optimised strict program will frequently outperform even the fastest non-strict program.<br />
<br />
However, the real and major advantage that non-strictness gives you over strict languages is you get to write cleaner and more composable code. In particular, you can separate ''production'' and ''consumption'' of data: don't know how many prime numbers you're going to need? Just make `primes` a list of ''all'' prime numbers, and then which ones actually get ''generated'' depends on how you use them in the rest of your code. By contrast, writing code in a strict language that constructs a data structure in response to demand usually will require careful intertwining or explicit management of control flow between the producer and consumer.<br />
<br />
Consider the following Haskell function definition:<br />
<br />
<haskell><br />
any :: (a -> Bool) -> [a] -> Bool<br />
any p = or . map p<br />
</haskell><br />
<br />
Here, <tt>map p</tt> replaces each element of the list with a boolean value representing whether or not that element satisfied <tt>p</tt>, then <tt>or</tt> checks if any of the booleans were <tt>True</tt>. Overall, then, <tt>any p xs</tt> tells you whether or not <tt>p x</tt> is <tt>True</tt> for any <tt>x</tt> in <tt>xs</tt>.<br />
<br />
Naively, it seems like this would be inefficient: first <tt>map</tt> processes the whole list, and then <tt>or</tt> finds any <tt>True</tt>s – but if the very first item of the list satisfies <tt>p</tt>, then you really didn't need to map over all the others.<br />
<br />
But in a non-strict context, even if both <tt>or</tt> and <tt>map</tt> are written completely naïvely, when <tt>or</tt> gets to the first <tt>True</tt> it stops asking for any more booleans, so <tt>map</tt> doesn't need to produce any more of them, and none of the rest of the list is visited.<br />
<br />
=== But that's so weird! ===<br />
<br />
Not really! In non-strict languages you typically have evaluation driven by need, whereas in strict languages you have evaluation driven by function application. But functions are already for abstraction, so they end up serving a sort of dual purpose; meanwhile ordinary values can't really be used for abstraction, except if you know you're going to use their value at least once. If you don't, you have to wrap your value in a function that doesn't take any arguments, or in certain type systems where that doesn't make sense as a concept, you have to use a function that takes a single, boring argument, that it then ignores. You then have to duplicate the work if you want to use it twice, or else write some sort of caching, probably using mutable variables. On top of all that, you decide that function application isn't even the only method of driving evaluation, because you also need if-statements, loops, and other control structures that you have to bake right into the fabric of your language.<br />
<br />
In a strict langauge, to get the short-circuiting behaviour of <tt>any</tt> described in the previous section, you'd have little choice but to write out the whole recursion explicitly:<br />
<br />
<haskell><br />
any p [] = False<br />
any p (x:xs)<br />
| p x = True<br />
| otherwise = any p xs<br />
</haskell><br />
<br />
since in strict languages only builtin control structures can decide whether some bit of code gets executed or not, ordinary functions like <tt>or</tt> can't. You essentially duplicate the code of <tt>map</tt> iterating over the list and applying a function, and <tt>or</tt> folding the list with a binary operation.<br />
<br />
Meanwhile, in Haskell, functions are precisely for abstraction with parameters, and for abstraction without parameters, ordinary values suffice, whether you end up using them or not. All code, inside or outside functions, gets run when you need it and doesn't when you don't. You can easily write control structures as ordinary code:<br />
<br />
<haskell><br />
ifThenElse :: Bool -> a -> a -> a<br />
ifThenElse True x _ = x<br />
ifThenElse False _ y = y<br />
</haskell><br />
<br />
and this allows all sorts of interesting patterns to be abstracted in an incredibly lightweight fashion. Labelled for-loops are a ''library'' in Haskell, rather than requiring special syntax and language support.<br />
<br />
== How do I stop it? ==<br />
<br />
As mentioned above, non-strictness can hurt performance, e.g. if a result is definitely going to be needed later, you might as well evaluate it now, to avoid having to hold on to all the data that goes into it. Fortunately, the Haskell designers were aware of these problems and introduced a loophole or two so that we could force our programs to be strict when necessary: see [[Performance/Strictness]] and [[seq]].<br />
<br />
[[Category:Glossary]]</div>Benmachinehttps://wiki.haskell.org/index.php?title=Non-strict_semantics&diff=63163Non-strict semantics2019-12-15T13:52:05Z<p>Benmachine: /* Why? */ more rephrases</p>
<hr />
<div>An expression language is said to have [[non-strict semantics]] if expressions can have a value even if some of their subexpressions do not. Haskell is one of the few modern languages to have non-strict semantics by default: nearly every other language has [[strict semantics]], in which if any subexpression fails to have a value, the whole expression fails with it.<br />
<br />
This is one of the most important features in Haskell: it is what allows programs to work with conceptually infinite data structures, and it is why people say that Haskell lets you write your own control structures. It's also one of the motivations behind Haskell being a [[pure]] language (though there are several other good ones).<br />
<br />
== What? ==<br />
<br />
Any sufficiently capable programming language is ''non-total'', which is to say you can write expressions that do not produce a value: common examples are an exception thrown, an infinite loop, or unproductive recursion, e.g. the following definition in Haskell:<br />
<br />
<haskell><br />
noreturn :: Integer -> Integer<br />
noreturn x = negate (noreturn x)<br />
</haskell><br />
<br />
or the following Python function:<br />
<br />
def noreturn(x):<br />
while True:<br />
x = -x<br />
<br />
return x # not reached<br />
<br />
both fail to produce a value when executed. We say that <tt>noreturn x</tt> is undefined, and write <tt>noreturn x = [[Bottom|⊥]]</tt>.<br />
<br />
In Python the following expression to check if <tt>2</tt> is in some list:<br />
<br />
2 in [2,4,noreturn(5)]<br />
<br />
also fails to have a value, because in order to construct the list, the interpreter tries to work out <tt>noreturn(5)</tt>, which of course doesn't return a value. This is called '''innermost-first''' evaluation: in order to call a function with some arguments, you first have to calculate what all the arguments are, starting from the innermost function call and working outwards. The result is that Python is ''strict'', in the sense that calling any function with an undefined argument produces an undefined value, i.e. <tt>f(⊥) = ⊥</tt>. If your language uses innermost-first evaluation, it correspondingly must have strict semantics.<br />
<br />
In Haskell, an analogous expression:<br />
<br />
<haskell><br />
elem 2 [2, 4, noreturn 5]<br />
</haskell><br />
<br />
in fact has the value <tt>True</tt>. The program does not have to compute <tt>noreturn 5</tt> because it is irrelevant to the overall value of the computation: only the values that are necessary to the result need be computed. This is called '''outermost-first''' evaluation because you first look at the outermost function call, <tt>elem</tt>, to see if it needs to use its arguments, and only if it does do you look at what those arguments are. This means that you can write a function that doesn't look at its argument, so it will return a value even if the argument is <tt>⊥</tt>. Such functions are ''not strict'', i.e. they satisfy <tt>f(⊥) ≠ ⊥</tt>. Practically, this means that Haskell functions need not completely compute their arguments before using them, which is why e.g. <tt>take 3 [1..]</tt> can produce <tt>[1,2,3]</tt> even though it is given a conceptually infinite list.<br />
<br />
Note that ''semantics'' is, pedantically speaking, just about which expressions have a value, and what the value is, not how you figure it out. Outermost-first evaluation is not the only way to have non-strict semantics: a speculative evaluation strategy, that evaluates arguments in parallel with the function in case they are needed later, could also be non-strict, as long as whenever the speculative evaluation failed, the evaluation of the function continued.<br />
<br />
Note also that according to the <tt>f(⊥) ≠ ⊥</tt> definition, lots of seemingly-nonstrict functions are actually strict, e.g. <tt>elem 2</tt> from the above example! However, strictness can be more nuanced than that: e.g. we can say that <tt>elem 2</tt> is non-strict in the part of the list following the first 2, so will return a non-⊥ answer to <tt>elem 2 (2 : ⊥)</tt>. We might say that a function is "strict in the spine of the list" (like <tt>length</tt>, which will ignore ⊥ in the elements of the list) or "strict in the second component of the tuple (like... <tt>snd</tt>, I guess).<br />
<br />
== Why? ==<br />
<br />
To correct a common misconception about non-strict semantics, it is not a performance feature. Non-strict semantics allows your language to only evaluate the things it needs to, but if you write your programs carefully, you'll only compute what is absolutely necessary ''anyway'', so the extra time your program spends working out what should and shouldn't be evaluated is time wasted. For this reason, a very well-optimised strict program will frequently outperform even the fastest non-strict program.<br />
<br />
However, the real and major advantage that non-strictness gives you over strict languages is you get to write cleaner and more composable code. In particular, you can separate ''production'' and ''consumption'' of data: don't know how many prime numbers you're going to need? Just make `primes` a list of ''all'' prime numbers, and then which ones actually get ''generated'' depends on how you use them in the rest of your code. By contrast, writing code in a strict language that constructs a data structure in response to demand usually will require careful intertwining or explicit management of control flow between the producer and consumer.<br />
<br />
Consider the following Haskell function definition:<br />
<br />
<haskell><br />
any :: (a -> Bool) -> [a] -> Bool<br />
any p = or . map p<br />
</haskell><br />
<br />
Here, <tt>map p</tt> replaces each element of the list with a boolean value representing whether or not that element satisfied <tt>p</tt>, then <tt>or</tt> checks if any of the booleans were <tt>True</tt>. Overall, then, <tt>any p xs</tt> tells you whether or not <tt>p x</tt> is <tt>True</tt> for any <tt>x</tt> in <tt>xs</tt>.<br />
<br />
Naively, it seems like this would be inefficient: first <tt>map</tt> processes the whole list, and then <tt>or</tt> finds any <tt>True</tt>s – but if the very first item of the list satisfies <tt>p</tt>, then you really didn't need to map over all the others.<br />
<br />
But in a non-strict context, even if both <tt>or</tt> and <tt>map</tt> are written completely naïvely, when <tt>or</tt> gets to the first <tt>True</tt> it stops asking for any more booleans, so <tt>map</tt> doesn't need to produce any more of them, and none of the rest of the list is visited.<br />
<br />
== But that's so weird! ==<br />
<br />
Not really! In non-strict languages you typically have evaluation driven by need, whereas in strict languages you have evaluation driven by function application. But functions are already for abstraction, so they end up serving a sort of dual purpose; meanwhile ordinary values can't really be used for abstraction, except if you know you're going to use their value at least once. If you don't, you have to wrap your value in a function that doesn't take any arguments, or in certain type systems where that doesn't make sense as a concept, you have to use a function that takes a single, boring argument, that it then ignores. You then have to duplicate the work if you want to use it twice, or else write some sort of caching, probably using mutable variables. On top of all that, you decide that function application isn't even the only method of driving evaluation, because you also need if-statements, loops, and other control structures that you have to bake right into the fabric of your language.<br />
<br />
In a strict langauge, to get the short-circuiting behaviour of <tt>any</tt> described in the previous section, you'd have little choice but to write out the whole recursion explicitly:<br />
<br />
<haskell><br />
any p [] = False<br />
any p (x:xs)<br />
| p x = True<br />
| otherwise = any p xs<br />
</haskell><br />
<br />
since in strict languages only builtin control structures can decide whether some bit of code gets executed or not, ordinary functions like <tt>or</tt> can't. You essentially duplicate the code of <tt>map</tt> iterating over the list and applying a function, and <tt>or</tt> folding the list with a binary operation.<br />
<br />
Meanwhile, in Haskell, functions are precisely for abstraction with parameters, and for abstraction without parameters, ordinary values suffice, whether you end up using them or not. All code, inside or outside functions, gets run when you need it and doesn't when you don't. You can easily write control structures as ordinary code:<br />
<br />
<haskell><br />
ifThenElse :: Bool -> a -> a -> a<br />
ifThenElse True x _ = x<br />
ifThenElse False _ y = y<br />
</haskell><br />
<br />
and this allows all sorts of interesting patterns to be abstracted in an incredibly lightweight fashion. Labelled for-loops are a ''library'' in Haskell, rather than requiring special syntax and language support.<br />
<br />
== How do I stop it? ==<br />
<br />
As mentioned above, non-strictness can hurt performance, e.g. if a result is definitely going to be needed later, you might as well evaluate it now, to avoid having to hold on to all the data that goes into it. Fortunately, the Haskell designers were aware of these problems and introduced a loophole or two so that we could force our programs to be strict when necessary: see [[Performance/Strictness]] and [[seq]].<br />
<br />
[[Category:Glossary]]</div>Benmachinehttps://wiki.haskell.org/index.php?title=Non-strict_semantics&diff=63162Non-strict semantics2019-12-15T13:50:59Z<p>Benmachine: /* Why? */ rephrase</p>
<hr />
<div>An expression language is said to have [[non-strict semantics]] if expressions can have a value even if some of their subexpressions do not. Haskell is one of the few modern languages to have non-strict semantics by default: nearly every other language has [[strict semantics]], in which if any subexpression fails to have a value, the whole expression fails with it.<br />
<br />
This is one of the most important features in Haskell: it is what allows programs to work with conceptually infinite data structures, and it is why people say that Haskell lets you write your own control structures. It's also one of the motivations behind Haskell being a [[pure]] language (though there are several other good ones).<br />
<br />
== What? ==<br />
<br />
Any sufficiently capable programming language is ''non-total'', which is to say you can write expressions that do not produce a value: common examples are an exception thrown, an infinite loop, or unproductive recursion, e.g. the following definition in Haskell:<br />
<br />
<haskell><br />
noreturn :: Integer -> Integer<br />
noreturn x = negate (noreturn x)<br />
</haskell><br />
<br />
or the following Python function:<br />
<br />
def noreturn(x):<br />
while True:<br />
x = -x<br />
<br />
return x # not reached<br />
<br />
both fail to produce a value when executed. We say that <tt>noreturn x</tt> is undefined, and write <tt>noreturn x = [[Bottom|⊥]]</tt>.<br />
<br />
In Python the following expression to check if <tt>2</tt> is in some list:<br />
<br />
2 in [2,4,noreturn(5)]<br />
<br />
also fails to have a value, because in order to construct the list, the interpreter tries to work out <tt>noreturn(5)</tt>, which of course doesn't return a value. This is called '''innermost-first''' evaluation: in order to call a function with some arguments, you first have to calculate what all the arguments are, starting from the innermost function call and working outwards. The result is that Python is ''strict'', in the sense that calling any function with an undefined argument produces an undefined value, i.e. <tt>f(⊥) = ⊥</tt>. If your language uses innermost-first evaluation, it correspondingly must have strict semantics.<br />
<br />
In Haskell, an analogous expression:<br />
<br />
<haskell><br />
elem 2 [2, 4, noreturn 5]<br />
</haskell><br />
<br />
in fact has the value <tt>True</tt>. The program does not have to compute <tt>noreturn 5</tt> because it is irrelevant to the overall value of the computation: only the values that are necessary to the result need be computed. This is called '''outermost-first''' evaluation because you first look at the outermost function call, <tt>elem</tt>, to see if it needs to use its arguments, and only if it does do you look at what those arguments are. This means that you can write a function that doesn't look at its argument, so it will return a value even if the argument is <tt>⊥</tt>. Such functions are ''not strict'', i.e. they satisfy <tt>f(⊥) ≠ ⊥</tt>. Practically, this means that Haskell functions need not completely compute their arguments before using them, which is why e.g. <tt>take 3 [1..]</tt> can produce <tt>[1,2,3]</tt> even though it is given a conceptually infinite list.<br />
<br />
Note that ''semantics'' is, pedantically speaking, just about which expressions have a value, and what the value is, not how you figure it out. Outermost-first evaluation is not the only way to have non-strict semantics: a speculative evaluation strategy, that evaluates arguments in parallel with the function in case they are needed later, could also be non-strict, as long as whenever the speculative evaluation failed, the evaluation of the function continued.<br />
<br />
Note also that according to the <tt>f(⊥) ≠ ⊥</tt> definition, lots of seemingly-nonstrict functions are actually strict, e.g. <tt>elem 2</tt> from the above example! However, strictness can be more nuanced than that: e.g. we can say that <tt>elem 2</tt> is non-strict in the part of the list following the first 2, so will return a non-⊥ answer to <tt>elem 2 (2 : ⊥)</tt>. We might say that a function is "strict in the spine of the list" (like <tt>length</tt>, which will ignore ⊥ in the elements of the list) or "strict in the second component of the tuple (like... <tt>snd</tt>, I guess).<br />
<br />
== Why? ==<br />
<br />
To correct a common misconception about non-strict semantics, it is not a performance feature. Non-strict semantics allows your language to only evaluate the things it needs to, but if you write your programs carefully, you'll only compute what is absolutely necessary ''anyway'', so the extra time your program spends working out what should and shouldn't be evaluated is time wasted. For this reason, a very well-optimised strict program will frequently outperform even the fastest non-strict program.<br />
<br />
However, the real and major advantage that non-strictness gives you over strict languages is you get to write cleaner and more composable code. In particular, you can separate ''production'' and ''consumption'' of data: don't know how many prime numbers you're going to need? Just make `primes` a list of ''all'' prime numbers, and then which ones actually get ''generated'' depends on how you use them in the rest of your code. By contrast, writing code in a strict language that constructs a data structure in response to demand usually will require first-class functions and/or a lot of manual hoop-jumping to make it all behave itself.<br />
<br />
Consider the following Haskell function definition:<br />
<br />
<haskell><br />
any :: (a -> Bool) -> [a] -> Bool<br />
any p = or . map p<br />
</haskell><br />
<br />
Here, <tt>map p</tt> replaces each element of the list with a boolean value representing whether or not that element satisfied <tt>p</tt>, then <tt>or</tt> checks if any of the booleans were <tt>True</tt>. Overall, then, <tt>any p xs</tt> tells you whether or not <tt>p x</tt> is <tt>True</tt> for any <tt>x</tt> in <tt>xs</tt>.<br />
<br />
Naively, it seems like this would be inefficient: first <tt>map</tt> processes the whole list, and then <tt>or</tt> finds any <tt>True</tt>s – but if the very first item of the list satisfies <tt>p</tt>, then you really didn't need to map over all the others.<br />
<br />
But in a non-strict context, even if both <tt>or</tt> and <tt>map</tt> are written completely naïvely, when <tt>or</tt> gets to the first <tt>True</tt> it stops asking for any more booleans, so <tt>map</tt> doesn't need to produce any more of them, and none of the rest of the list is visited.<br />
<br />
== But that's so weird! ==<br />
<br />
Not really! In non-strict languages you typically have evaluation driven by need, whereas in strict languages you have evaluation driven by function application. But functions are already for abstraction, so they end up serving a sort of dual purpose; meanwhile ordinary values can't really be used for abstraction, except if you know you're going to use their value at least once. If you don't, you have to wrap your value in a function that doesn't take any arguments, or in certain type systems where that doesn't make sense as a concept, you have to use a function that takes a single, boring argument, that it then ignores. You then have to duplicate the work if you want to use it twice, or else write some sort of caching, probably using mutable variables. On top of all that, you decide that function application isn't even the only method of driving evaluation, because you also need if-statements, loops, and other control structures that you have to bake right into the fabric of your language.<br />
<br />
In a strict langauge, to get the short-circuiting behaviour of <tt>any</tt> described in the previous section, you'd have little choice but to write out the whole recursion explicitly:<br />
<br />
<haskell><br />
any p [] = False<br />
any p (x:xs)<br />
| p x = True<br />
| otherwise = any p xs<br />
</haskell><br />
<br />
since in strict languages only builtin control structures can decide whether some bit of code gets executed or not, ordinary functions like <tt>or</tt> can't. You essentially duplicate the code of <tt>map</tt> iterating over the list and applying a function, and <tt>or</tt> folding the list with a binary operation.<br />
<br />
Meanwhile, in Haskell, functions are precisely for abstraction with parameters, and for abstraction without parameters, ordinary values suffice, whether you end up using them or not. All code, inside or outside functions, gets run when you need it and doesn't when you don't. You can easily write control structures as ordinary code:<br />
<br />
<haskell><br />
ifThenElse :: Bool -> a -> a -> a<br />
ifThenElse True x _ = x<br />
ifThenElse False _ y = y<br />
</haskell><br />
<br />
and this allows all sorts of interesting patterns to be abstracted in an incredibly lightweight fashion. Labelled for-loops are a ''library'' in Haskell, rather than requiring special syntax and language support.<br />
<br />
== How do I stop it? ==<br />
<br />
As mentioned above, non-strictness can hurt performance, e.g. if a result is definitely going to be needed later, you might as well evaluate it now, to avoid having to hold on to all the data that goes into it. Fortunately, the Haskell designers were aware of these problems and introduced a loophole or two so that we could force our programs to be strict when necessary: see [[Performance/Strictness]] and [[seq]].<br />
<br />
[[Category:Glossary]]</div>Benmachinehttps://wiki.haskell.org/index.php?title=Non-strict_semantics&diff=63161Non-strict semantics2019-12-15T13:49:51Z<p>Benmachine: clarified / rewrote two paragraphs</p>
<hr />
<div>An expression language is said to have [[non-strict semantics]] if expressions can have a value even if some of their subexpressions do not. Haskell is one of the few modern languages to have non-strict semantics by default: nearly every other language has [[strict semantics]], in which if any subexpression fails to have a value, the whole expression fails with it.<br />
<br />
This is one of the most important features in Haskell: it is what allows programs to work with conceptually infinite data structures, and it is why people say that Haskell lets you write your own control structures. It's also one of the motivations behind Haskell being a [[pure]] language (though there are several other good ones).<br />
<br />
== What? ==<br />
<br />
Any sufficiently capable programming language is ''non-total'', which is to say you can write expressions that do not produce a value: common examples are an exception thrown, an infinite loop, or unproductive recursion, e.g. the following definition in Haskell:<br />
<br />
<haskell><br />
noreturn :: Integer -> Integer<br />
noreturn x = negate (noreturn x)<br />
</haskell><br />
<br />
or the following Python function:<br />
<br />
def noreturn(x):<br />
while True:<br />
x = -x<br />
<br />
return x # not reached<br />
<br />
both fail to produce a value when executed. We say that <tt>noreturn x</tt> is undefined, and write <tt>noreturn x = [[Bottom|⊥]]</tt>.<br />
<br />
In Python the following expression to check if <tt>2</tt> is in some list:<br />
<br />
2 in [2,4,noreturn(5)]<br />
<br />
also fails to have a value, because in order to construct the list, the interpreter tries to work out <tt>noreturn(5)</tt>, which of course doesn't return a value. This is called '''innermost-first''' evaluation: in order to call a function with some arguments, you first have to calculate what all the arguments are, starting from the innermost function call and working outwards. The result is that Python is ''strict'', in the sense that calling any function with an undefined argument produces an undefined value, i.e. <tt>f(⊥) = ⊥</tt>. If your language uses innermost-first evaluation, it correspondingly must have strict semantics.<br />
<br />
In Haskell, an analogous expression:<br />
<br />
<haskell><br />
elem 2 [2, 4, noreturn 5]<br />
</haskell><br />
<br />
in fact has the value <tt>True</tt>. The program does not have to compute <tt>noreturn 5</tt> because it is irrelevant to the overall value of the computation: only the values that are necessary to the result need be computed. This is called '''outermost-first''' evaluation because you first look at the outermost function call, <tt>elem</tt>, to see if it needs to use its arguments, and only if it does do you look at what those arguments are. This means that you can write a function that doesn't look at its argument, so it will return a value even if the argument is <tt>⊥</tt>. Such functions are ''not strict'', i.e. they satisfy <tt>f(⊥) ≠ ⊥</tt>. Practically, this means that Haskell functions need not completely compute their arguments before using them, which is why e.g. <tt>take 3 [1..]</tt> can produce <tt>[1,2,3]</tt> even though it is given a conceptually infinite list.<br />
<br />
Note that ''semantics'' is, pedantically speaking, just about which expressions have a value, and what the value is, not how you figure it out. Outermost-first evaluation is not the only way to have non-strict semantics: a speculative evaluation strategy, that evaluates arguments in parallel with the function in case they are needed later, could also be non-strict, as long as whenever the speculative evaluation failed, the evaluation of the function continued.<br />
<br />
Note also that according to the <tt>f(⊥) ≠ ⊥</tt> definition, lots of seemingly-nonstrict functions are actually strict, e.g. <tt>elem 2</tt> from the above example! However, strictness can be more nuanced than that: e.g. we can say that <tt>elem 2</tt> is non-strict in the part of the list following the first 2, so will return a non-⊥ answer to <tt>elem 2 (2 : ⊥)</tt>. We might say that a function is "strict in the spine of the list" (like <tt>length</tt>, which will ignore ⊥ in the elements of the list) or "strict in the second component of the tuple (like... <tt>snd</tt>, I guess).<br />
<br />
== Why? ==<br />
<br />
The important thing to understand about non-strict semantics is that it is not a performance feature. Non-strict semantics allows your language to only evaluate the things it needs to, but if you write your programs carefully, you'll only compute what is absolutely necessary ''anyway'', so the extra time your program spends working out what should and shouldn't be evaluated is time wasted. For this reason, a very well-optimised strict program will frequently outperform even the fastest non-strict program.<br />
<br />
However, the real and major advantage that non-strictness gives you over strict languages is you get to write cleaner and more composable code. In particular, you can separate ''production'' and ''consumption'' of data: don't know how many prime numbers you're going to need? Just make `primes` a list of ''all'' prime numbers, and then which ones actually get ''generated'' depends on how you use them in the rest of your code. By contrast, writing code in a strict language that constructs a data structure in response to demand usually will require first-class functions and/or a lot of manual hoop-jumping to make it all behave itself.<br />
<br />
Consider the following Haskell function definition:<br />
<br />
<haskell><br />
any :: (a -> Bool) -> [a] -> Bool<br />
any p = or . map p<br />
</haskell><br />
<br />
Here, <tt>map p</tt> replaces each element of the list with a boolean value representing whether or not that element satisfied <tt>p</tt>, then <tt>or</tt> checks if any of the booleans were <tt>True</tt>. Overall, then, <tt>any p xs</tt> tells you whether or not <tt>p x</tt> is <tt>True</tt> for any <tt>x</tt> in <tt>xs</tt>.<br />
<br />
Naively, it seems like this would be inefficient: first <tt>map</tt> processes the whole list, and then <tt>or</tt> finds any <tt>True</tt>s – but if the very first item of the list satisfies <tt>p</tt>, then you really didn't need to map over all the others.<br />
<br />
But in a non-strict context, even if both <tt>or</tt> and <tt>map</tt> are written completely naïvely, when <tt>or</tt> gets to the first <tt>True</tt> it stops asking for any more booleans, so <tt>map</tt> doesn't need to produce any more of them, and none of the rest of the list is visited.<br />
<br />
== But that's so weird! ==<br />
<br />
Not really! In non-strict languages you typically have evaluation driven by need, whereas in strict languages you have evaluation driven by function application. But functions are already for abstraction, so they end up serving a sort of dual purpose; meanwhile ordinary values can't really be used for abstraction, except if you know you're going to use their value at least once. If you don't, you have to wrap your value in a function that doesn't take any arguments, or in certain type systems where that doesn't make sense as a concept, you have to use a function that takes a single, boring argument, that it then ignores. You then have to duplicate the work if you want to use it twice, or else write some sort of caching, probably using mutable variables. On top of all that, you decide that function application isn't even the only method of driving evaluation, because you also need if-statements, loops, and other control structures that you have to bake right into the fabric of your language.<br />
<br />
In a strict langauge, to get the short-circuiting behaviour of <tt>any</tt> described in the previous section, you'd have little choice but to write out the whole recursion explicitly:<br />
<br />
<haskell><br />
any p [] = False<br />
any p (x:xs)<br />
| p x = True<br />
| otherwise = any p xs<br />
</haskell><br />
<br />
since in strict languages only builtin control structures can decide whether some bit of code gets executed or not, ordinary functions like <tt>or</tt> can't. You essentially duplicate the code of <tt>map</tt> iterating over the list and applying a function, and <tt>or</tt> folding the list with a binary operation.<br />
<br />
Meanwhile, in Haskell, functions are precisely for abstraction with parameters, and for abstraction without parameters, ordinary values suffice, whether you end up using them or not. All code, inside or outside functions, gets run when you need it and doesn't when you don't. You can easily write control structures as ordinary code:<br />
<br />
<haskell><br />
ifThenElse :: Bool -> a -> a -> a<br />
ifThenElse True x _ = x<br />
ifThenElse False _ y = y<br />
</haskell><br />
<br />
and this allows all sorts of interesting patterns to be abstracted in an incredibly lightweight fashion. Labelled for-loops are a ''library'' in Haskell, rather than requiring special syntax and language support.<br />
<br />
== How do I stop it? ==<br />
<br />
As mentioned above, non-strictness can hurt performance, e.g. if a result is definitely going to be needed later, you might as well evaluate it now, to avoid having to hold on to all the data that goes into it. Fortunately, the Haskell designers were aware of these problems and introduced a loophole or two so that we could force our programs to be strict when necessary: see [[Performance/Strictness]] and [[seq]].<br />
<br />
[[Category:Glossary]]</div>Benmachinehttps://wiki.haskell.org/index.php?title=Non-strict_semantics&diff=63160Non-strict semantics2019-12-15T13:08:13Z<p>Benmachine: correct link destination</p>
<hr />
<div>An expression language is said to have [[non-strict semantics]] if expressions can have a value even if some of their subexpressions do not. Haskell is one of the few modern languages to have non-strict semantics by default: nearly every other language has [[strict semantics]], in which if any subexpression fails to have a value, the whole expression fails with it.<br />
<br />
This is one of the most important features in Haskell: it is what allows programs to work with conceptually infinite data structures, and it is why people say that Haskell lets you write your own control structures. It's also one of the motivations behind Haskell being a [[pure]] language (though there are several other good ones).<br />
<br />
== What? ==<br />
<br />
Any sufficiently capable programming language is ''non-total'', which is to say you can write expressions that do not produce a value: common examples are an exception thrown, an infinite loop, or unproductive recursion, e.g. the following definition in Haskell:<br />
<br />
<haskell><br />
noreturn :: Integer -> Integer<br />
noreturn x = negate (noreturn x)<br />
</haskell><br />
<br />
or the following Python function:<br />
<br />
def noreturn(x):<br />
while True:<br />
x = -x<br />
<br />
return x # not reached<br />
<br />
both fail to produce a value when executed. We say that <tt>noreturn x</tt> is undefined, and write <tt>noreturn x = [[Bottom|⊥]]</tt>.<br />
<br />
In Python the following expression to check if <tt>2</tt> is in some list:<br />
<br />
2 in [2,4,noreturn(5)]<br />
<br />
also fails to have a value, because in order to construct the list, the interpreter tries to work out <tt>noreturn(5)</tt>, which of course doesn't return a value. This is called '''innermost-first''' evaluation: in order to call a function with some arguments, you first have to calculate what all the arguments are, starting from the innermost function call and working outwards. The result is that Python is ''strict'', in the sense that calling any function with an undefined argument produces an undefined value, i.e. <tt>f(⊥) = ⊥</tt>. If your language uses innermost-first evaluation, it correspondingly must have strict semantics.<br />
<br />
In Haskell, an analogous expression:<br />
<br />
<haskell><br />
elem 2 [2, 4, noreturn 5]<br />
</haskell><br />
<br />
in fact has the value <tt>True</tt>. The program does not have to compute <tt>noreturn 5</tt> because it is irrelevant to the overall value of the computation: only the values that are necessary to the result need be computed. This is called '''outermost-first''' evaluation because you first look at the outermost function call, <tt>elem</tt>, to see if it needs to use its arguments, and only if it does do you look at what those arguments are. This means that you can write a function that doesn't look at its argument, so it will return a value even if the argument is <tt>⊥</tt>. Such functions are ''not strict'', i.e. they satisfy <tt>f(⊥) ≠ ⊥</tt>. Practically, this means that Haskell functions need not completely compute their arguments before using them, which is why e.g. <tt>take 3 [1..]</tt> can produce <tt>[1,2,3]</tt> even though it is given a conceptually infinite list.<br />
<br />
Note that outermost-first evaluation is not the only way to have non-strict semantics: a speculative evaluation strategy, that evaluates arguments in parallel with the function in case they are needed later, could also be non-strict, as long as whenever the speculative evaluation failed, the evaluation of the function continued.<br />
<br />
Note also that in order for a function to be truly non-strict, it must return something without inspecting its argument ''at all''. You might think that doesn't sound like a very useful function, but remember that it might be e.g. a partial application: the function <tt>(||) True</tt>, or equivalently <tt>\x -> True || x</tt> does not need to inspect its argument, since <tt>True || x</tt> is always <tt>True</tt>. There are other examples, too: constructors like <tt>Just</tt> wrap their argument without inspecting it, and some other functions apply constructors before looking at the argument, and hence still produce a partial result, e.g. <tt>inits ⊥ = [] : ⊥</tt><br />
<br />
== Why? ==<br />
<br />
The important thing to understand about non-strict semantics is that it is not a performance feature. Non-strict semantics allows your language to only evaluate the things it needs to, but if you write your programs carefully, you'll only compute what is absolutely necessary ''anyway'', so the extra time your program spends working out what should and shouldn't be evaluated is time wasted. For this reason, a very well-optimised strict program will frequently outperform even the fastest non-strict program.<br />
<br />
However, the real and major advantage that non-strictness gives you over strict languages is you get to write cleaner and more composable code. In particular, you can separate ''production'' and ''consumption'' of data: don't know how many prime numbers you're going to need? Just make `primes` a list of ''all'' prime numbers, and then which ones actually get ''generated'' depends on how you use them in the rest of your code. By contrast, writing code in a strict language that constructs a data structure in response to demand usually will require first-class functions and/or a lot of manual hoop-jumping to make it all behave itself.<br />
<br />
Consider the following Haskell function definition:<br />
<br />
<haskell><br />
any :: (a -> Bool) -> [a] -> Bool<br />
any p = or . map p<br />
</haskell><br />
<br />
Here, <tt>map p</tt> replaces each element of the list with a boolean value representing whether or not that element satisfied <tt>p</tt>, then <tt>or</tt> checks if any of the booleans were <tt>True</tt>. Overall, then, <tt>any p xs</tt> tells you whether or not <tt>p x</tt> is <tt>True</tt> for any <tt>x</tt> in <tt>xs</tt>.<br />
<br />
Naively, it seems like this would be inefficient: first <tt>map</tt> processes the whole list, and then <tt>or</tt> finds any <tt>True</tt>s – but if the very first item of the list satisfies <tt>p</tt>, then you really didn't need to map over all the others.<br />
<br />
But in a non-strict context, even if both <tt>or</tt> and <tt>map</tt> are written completely naïvely, when <tt>or</tt> gets to the first <tt>True</tt> it stops asking for any more booleans, so <tt>map</tt> doesn't need to produce any more of them, and none of the rest of the list is visited.<br />
<br />
== But that's so weird! ==<br />
<br />
Not really! In non-strict languages you typically have evaluation driven by need, whereas in strict languages you have evaluation driven by function application. But functions are already for abstraction, so they end up serving a sort of dual purpose; meanwhile ordinary values can't really be used for abstraction, except if you know you're going to use their value at least once. If you don't, you have to wrap your value in a function that doesn't take any arguments, or in certain type systems where that doesn't make sense as a concept, you have to use a function that takes a single, boring argument, that it then ignores. You then have to duplicate the work if you want to use it twice, or else write some sort of caching, probably using mutable variables. On top of all that, you decide that function application isn't even the only method of driving evaluation, because you also need if-statements, loops, and other control structures that you have to bake right into the fabric of your language.<br />
<br />
In a strict langauge, to get the short-circuiting behaviour of <tt>any</tt> described in the previous section, you'd have little choice but to write out the whole recursion explicitly:<br />
<br />
<haskell><br />
any p [] = False<br />
any p (x:xs)<br />
| p x = True<br />
| otherwise = any p xs<br />
</haskell><br />
<br />
since in strict languages only builtin control structures can decide whether some bit of code gets executed or not, ordinary functions like <tt>or</tt> can't. You essentially duplicate the code of <tt>map</tt> iterating over the list and applying a function, and <tt>or</tt> folding the list with a binary operation.<br />
<br />
Meanwhile, in Haskell, functions are precisely for abstraction with parameters, and for abstraction without parameters, ordinary values suffice, whether you end up using them or not. All code, inside or outside functions, gets run when you need it and doesn't when you don't. You can easily write control structures as ordinary code:<br />
<br />
<haskell><br />
ifThenElse :: Bool -> a -> a -> a<br />
ifThenElse True x _ = x<br />
ifThenElse False _ y = y<br />
</haskell><br />
<br />
and this allows all sorts of interesting patterns to be abstracted in an incredibly lightweight fashion. Labelled for-loops are a ''library'' in Haskell, rather than requiring special syntax and language support.<br />
<br />
== How do I stop it? ==<br />
<br />
As mentioned above, non-strictness can hurt performance, e.g. if a result is definitely going to be needed later, you might as well evaluate it now, to avoid having to hold on to all the data that goes into it. Fortunately, the Haskell designers were aware of these problems and introduced a loophole or two so that we could force our programs to be strict when necessary: see [[Performance/Strictness]] and [[seq]].<br />
<br />
[[Category:Glossary]]</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine&diff=60328User:Benmachine2015-11-02T14:11:50Z<p>Benmachine: newtype draft</p>
<hr />
<div>I found a [[User:benmachine/hasktag_bug|bug with the &lt;hask&gt; tag]]. I put it on its own page so it doesn't ruin my user page.<br />
<br />
I wrote a [[User:benmachine/Cont|Cont tutorial]] of sorts.<br />
<br />
I have some objections to [[User:benmachine/Overqualified modules|module overqualification]]<br />
<br />
I wrote an [[User:benmachine/uninstall.sh|uninstall script]] for things cabal installs.<br />
<br />
Draft space:<br />
<br />
= Newtype =<br />
<br />
A '''newtype''' declaration creates a fresh type with the same representation as an existing ("underlying") type. The most common reasons they are used are:<br />
<br />
* providing additional type safety, by making different uses of the same underlying type incompatible,<br />
* creating abstract data types,<br />
* permitting alternative or additional typeclass instances to be declared for the new type.<br />
<br />
== Syntax ==<br />
<br />
The syntax is similar to that of [[data]] declarations:<br />
<br />
<haskell><br />
-- name of the new type<br />
-- | name of its value constructor<br />
-- | | underlying type<br />
-- | | |<br />
-- v v v<br />
newtype Username = MkUsername String<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
-- may also have type parameters<br />
newtype Parser a = MkParser (String -> Maybe (String, a))<br />
<br />
-- or record syntax<br />
newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }<br />
</haskell><br />
<br />
Following the above declarations, we have new type constructors <hask>Username</hask>, <hask>Parser</hask>, and <hask>StateT</hask>, and new value constructors with the following types:<br />
<br />
<haskell><br />
MkUsername :: String -> Username<br />
MkParser :: (String -> Maybe (String, a)) -> Parser a<br />
<br />
StateT :: (s -> m (a, s)) -> StateT s m a<br />
runStateT :: StateT s m a -> (s -> m (a, s))<br />
</haskell><br />
<br />
Notice that in the case of StateT, the type constructor and the value constructor have the same name: some find that this is a helpful mnemonic, while others find it confusing, and insist on something like the <tt>Mk</tt> prefix used above (both these conventions also exist for single-constructor data declarations).<br />
<br />
By contrast to data declarations, which may have several value constructors, each with zero or more fields containing values of other types, newtypes may only have exactly one constructor, and that constructor must have exactly one field (which, as shown above, is permitted to be a record field). This ensures that the new type and the underlying type – the type of that single field of that single constructor – are in direct correspondence.<br />
<br />
== Uses ==<br />
<br />
So, if a newtype declaration can only create a type that's exactly the same as an existing type, why bother at all? Let's return to the three bullet points given at the start of the article:<br />
<br />
=== Additional type safety ===<br />
<br />
Sometimes you use one type for many different purposes, and it's important not to get them mixed up.</div>Benmachinehttps://wiki.haskell.org/index.php?title=Monoid&diff=60323Monoid2015-11-01T16:52:39Z<p>Benmachine: /* On the Writer monad */ trim unhelpful remark</p>
<hr />
<div>In Haskell, the Monoid typeclass (not to be confused with [[Monad]]) is a class for types which have a single most natural operation for combining values, together with a value which doesn't do anything when you combine it with others (this is called the ''identity'' element). It is closely related to the [[Foldable]] class, and indeed you can think of a Monoid instance declaration for a type ''m'' as precisely what you need in order to fold up a list of values of ''m''.<br />
<br />
== The basics ==<br />
<br />
=== Declaration ===<br />
<br />
<haskell><br />
class Monoid m where<br />
mempty :: m<br />
mappend :: m -> m -> m<br />
mconcat :: [m] -> m<br />
-- defining mconcat is optional, since it has the following default:<br />
mconcat = foldr mappend mempty<br />
<br />
-- this infix synonym for mappend is found in Data.Monoid<br />
x <> y = mappend x y<br />
infixr 6 <><br />
</haskell><br />
<br />
together with the following laws:<br />
<br />
<haskell><br />
-- Identity laws<br />
x <> mempty = x<br />
mempty <> x = x<br />
<br />
-- Associativity<br />
(x <> y) <> z = x <> (y <> z)<br />
</haskell><br />
<br />
=== Examples ===<br />
<br />
The prototypical and perhaps most important example is lists, which form a monoid under concatenation:<br />
<br />
<haskell><br />
instance Monoid [a] where<br />
mempty = []<br />
mappend x y = x ++ y<br />
mconcat = concat<br />
</haskell><br />
<br />
Indeed, appending the empty list to either end of an existing list does nothing, and <hask>(x ++ y) ++ z</hask> and <hask>x ++ (y ++ z)</hask> are both the same list, namely all the elements of <hask>x</hask>, then all the elements of <hask>y</hask>, them all the elements of <hask>z</hask>.<br />
<br />
Numbers also form a monoid under addition, with 0 the identity element, but they also form a monoid under multiplication, with 1 the identity element. Neither of these instances are really more natural than the other, so we use the [[newtype]]s <tt>Sum n</tt> and <tt>Product n</tt> to distinguish between them:<br />
<br />
<haskell><br />
newtype Sum n = Sum n<br />
<br />
instance Num n => Monoid (Sum n) where<br />
mempty = Sum 0<br />
mappend (Sum x) (Sum y) = Sum (x + y)<br />
<br />
newtype Product n = Product n<br />
<br />
instance Num n => Monoid (Product n) where<br />
mempty = Sum 1<br />
mappend (Sum x) (Sum y) = Sum (x * y)<br />
</haskell><br />
<br />
Now <hask>mconcat</hask> on a list of <hask>Sum Integer</hask> (say) values works like <hask>sum</hask>, while on a list of <hask>Product Double</hask> values it works like <hask>product</hask>.<br />
<br />
=== So what? ===<br />
<br />
There are several reasons why you want a typeclass for combining things, e.g. because it couples well with other typeclasses (the aforementioned [[Foldable]], or the [[Writer monad]], or some [[Applicative]]s). But for a rather striking example of what Monoid can do alone, you can look at the way its instances can work together. First, <hask>Ordering</hask>, the standard type which Haskell uses for the result of <hask>compare</hask> functions, has a "lexicographic" combination operation, where <hask>mappend</hask> essentially takes the first non-equality result. Secondly, if <hask>b</hask> is a Monoid, then functions of type <hask>a -> b</hask> can be combined by just calling them both and combining the results. Now, of course, since <hask>a -> a -> b</hask> is just a function returning a function, it can also be combined in the same way, and so you can combine comparison functions, of type <hask>a -> a -> Ordering</hask>, and write the following sorts of thing, which means "sort strings by length and then alphabetically":<br />
<br />
<haskell><br />
sortStrings = sortBy (comparing length <> compare)<br />
</haskell><br />
<br />
Isn't that wonderfully descriptive? And we didn't write any functions specifically to do this – it's just composed of simple, reusable parts.<br />
<br />
== In more depth ==<br />
<br />
=== On mconcat ===<br />
<br />
mconcat is often presented as just an optimisation, only in the class so that people can define more efficient versions of it. That's true in a sense, but note that mempty and mappend can just as well be defined in terms of mconcat:<br />
<br />
<haskell><br />
mempty = mconcat []<br />
mappend x y = mconcat [x, y]<br />
</haskell><br />
<br />
What of the laws? Well, we can have the following:<br />
<br />
<haskell><br />
mconcat [x] = x<br />
mconcat (map mconcat xss) = mconcat (concat xss)<br />
</haskell><br />
<br />
The first rule is natural enough. The second rule is a little more subtle, but basically says that if you have a list of lists of some monoidy things, and you mconcat each sublist individually, then mconcat all the results, that's just the same as if you had squashed all the sublists together first, and mconcatted the result of that. Or in other words, it's telling you something like what associativity tells you, that the order in which you fold up a list doesn't matter.<br />
<br />
==== Categorical diversion ====<br />
<br />
Note that the above two laws can also be phrased as follows:<br />
<br />
<haskell><br />
mconcat . return = id<br />
mconcat . map mconcat = mconcat . join<br />
</haskell><br />
<br />
In [[category theory]] terms, this is exactly the condition for <hask>mconcat</hask> to be a monad algebra for the list monad.<br />
<br />
=== On the Writer monad ===<br />
<br />
The [[Writer monad]] is a way to put a monad structure on tuples. You write bind like this:<br />
<br />
<haskell><br />
(w,x) >>= f =<br />
case f x of<br />
(v, y) -> (w <> v, y)<br />
</haskell><br />
<br />
Notice that it's the monoid instance of the first component that allows you to incorporate both <tt>w</tt> and <tt>v</tt> into the final result, which seems like an important thing to do.<br />
<br />
You might, however, wonder if there's not some other way to get a law-abiding monad. The answer is essentially no: if <hask>(w,a)</hask> is a monad, you can use its monad instance to write a monoid instance for <hask>w</hask>: basically <hask>mempty = fst (return ())</hask> and <hask>mappend x y = fst (join (x,(y,()))</hask>, and the monad laws ensure associativity and identity. So in fact, monoids are exactly what you need to make a monad structure on tuples.<br />
<br />
=== On the Const applicative ===<br />
<br />
Even more straightforwardly, <hask>Const m</hask> is applicative precisely when <hask>m</hask> is a monoid.<br />
<br />
== See also ==<br />
<br />
* [http://sigfpe.blogspot.com/2009/01/haskell-monoids-and-their-uses.html Haskell Monoids and their Uses]<br />
* [http://apfelmus.nfshost.com/monoid-fingertree.html Monoids and Finger Trees]<br />
* [http://haskell.org/sitewiki/images/6/6a/TMR-Issue11.pdf Monad.Reader issue 11, "How to Refold a Map."] (PDF), and a [http://haskell.org/haskellwiki/The_Monad.Reader/Discuss_Issue11 follow up]<br />
<br />
Generalizations of monoids feature in [[Category theory]], for example:<br />
* [http://www.researchgate.net/publication/235540658_Arrows_like_Monads_are_Monoids/file/d912f511ccdf2c1016.pdf Arrows, like Monads, are Monoids] (PDF)</div>Benmachinehttps://wiki.haskell.org/index.php?title=Monoid&diff=60322Monoid2015-11-01T16:51:23Z<p>Benmachine: /* On the Writer monad */ avoid single quotes</p>
<hr />
<div>In Haskell, the Monoid typeclass (not to be confused with [[Monad]]) is a class for types which have a single most natural operation for combining values, together with a value which doesn't do anything when you combine it with others (this is called the ''identity'' element). It is closely related to the [[Foldable]] class, and indeed you can think of a Monoid instance declaration for a type ''m'' as precisely what you need in order to fold up a list of values of ''m''.<br />
<br />
== The basics ==<br />
<br />
=== Declaration ===<br />
<br />
<haskell><br />
class Monoid m where<br />
mempty :: m<br />
mappend :: m -> m -> m<br />
mconcat :: [m] -> m<br />
-- defining mconcat is optional, since it has the following default:<br />
mconcat = foldr mappend mempty<br />
<br />
-- this infix synonym for mappend is found in Data.Monoid<br />
x <> y = mappend x y<br />
infixr 6 <><br />
</haskell><br />
<br />
together with the following laws:<br />
<br />
<haskell><br />
-- Identity laws<br />
x <> mempty = x<br />
mempty <> x = x<br />
<br />
-- Associativity<br />
(x <> y) <> z = x <> (y <> z)<br />
</haskell><br />
<br />
=== Examples ===<br />
<br />
The prototypical and perhaps most important example is lists, which form a monoid under concatenation:<br />
<br />
<haskell><br />
instance Monoid [a] where<br />
mempty = []<br />
mappend x y = x ++ y<br />
mconcat = concat<br />
</haskell><br />
<br />
Indeed, appending the empty list to either end of an existing list does nothing, and <hask>(x ++ y) ++ z</hask> and <hask>x ++ (y ++ z)</hask> are both the same list, namely all the elements of <hask>x</hask>, then all the elements of <hask>y</hask>, them all the elements of <hask>z</hask>.<br />
<br />
Numbers also form a monoid under addition, with 0 the identity element, but they also form a monoid under multiplication, with 1 the identity element. Neither of these instances are really more natural than the other, so we use the [[newtype]]s <tt>Sum n</tt> and <tt>Product n</tt> to distinguish between them:<br />
<br />
<haskell><br />
newtype Sum n = Sum n<br />
<br />
instance Num n => Monoid (Sum n) where<br />
mempty = Sum 0<br />
mappend (Sum x) (Sum y) = Sum (x + y)<br />
<br />
newtype Product n = Product n<br />
<br />
instance Num n => Monoid (Product n) where<br />
mempty = Sum 1<br />
mappend (Sum x) (Sum y) = Sum (x * y)<br />
</haskell><br />
<br />
Now <hask>mconcat</hask> on a list of <hask>Sum Integer</hask> (say) values works like <hask>sum</hask>, while on a list of <hask>Product Double</hask> values it works like <hask>product</hask>.<br />
<br />
=== So what? ===<br />
<br />
There are several reasons why you want a typeclass for combining things, e.g. because it couples well with other typeclasses (the aforementioned [[Foldable]], or the [[Writer monad]], or some [[Applicative]]s). But for a rather striking example of what Monoid can do alone, you can look at the way its instances can work together. First, <hask>Ordering</hask>, the standard type which Haskell uses for the result of <hask>compare</hask> functions, has a "lexicographic" combination operation, where <hask>mappend</hask> essentially takes the first non-equality result. Secondly, if <hask>b</hask> is a Monoid, then functions of type <hask>a -> b</hask> can be combined by just calling them both and combining the results. Now, of course, since <hask>a -> a -> b</hask> is just a function returning a function, it can also be combined in the same way, and so you can combine comparison functions, of type <hask>a -> a -> Ordering</hask>, and write the following sorts of thing, which means "sort strings by length and then alphabetically":<br />
<br />
<haskell><br />
sortStrings = sortBy (comparing length <> compare)<br />
</haskell><br />
<br />
Isn't that wonderfully descriptive? And we didn't write any functions specifically to do this – it's just composed of simple, reusable parts.<br />
<br />
== In more depth ==<br />
<br />
=== On mconcat ===<br />
<br />
mconcat is often presented as just an optimisation, only in the class so that people can define more efficient versions of it. That's true in a sense, but note that mempty and mappend can just as well be defined in terms of mconcat:<br />
<br />
<haskell><br />
mempty = mconcat []<br />
mappend x y = mconcat [x, y]<br />
</haskell><br />
<br />
What of the laws? Well, we can have the following:<br />
<br />
<haskell><br />
mconcat [x] = x<br />
mconcat (map mconcat xss) = mconcat (concat xss)<br />
</haskell><br />
<br />
The first rule is natural enough. The second rule is a little more subtle, but basically says that if you have a list of lists of some monoidy things, and you mconcat each sublist individually, then mconcat all the results, that's just the same as if you had squashed all the sublists together first, and mconcatted the result of that. Or in other words, it's telling you something like what associativity tells you, that the order in which you fold up a list doesn't matter.<br />
<br />
==== Categorical diversion ====<br />
<br />
Note that the above two laws can also be phrased as follows:<br />
<br />
<haskell><br />
mconcat . return = id<br />
mconcat . map mconcat = mconcat . join<br />
</haskell><br />
<br />
In [[category theory]] terms, this is exactly the condition for <hask>mconcat</hask> to be a monad algebra for the list monad.<br />
<br />
=== On the Writer monad ===<br />
<br />
The [[Writer monad]] is a way to put a monad structure on tuples. You write bind like this:<br />
<br />
<haskell><br />
(w,x) >>= f =<br />
case f x of<br />
(v, y) -> (w <> v, y)<br />
</haskell><br />
<br />
Notice that it's the monoid instance of the first component that allows you to incorporate both <tt>w</tt> and <tt>v</tt> into the final result, which seems like an important thing to do.<br />
<br />
You might, however, wonder if there's not some other way to get a law-abiding monad. The answer is essentially no: if <hask>(w,a)</hask> is a monad, you can use its monad instance to write a monoid instance for <hask>w</hask>: basically <hask>mempty = fst (return ())</hask> and <hask>mappend x y = fst (join (x,(y,()))</hask>, and the monad laws ensure associativity and identity. So in fact, monoids and monad structures on tuples are again in exact correspondence. Monoids really get around!<br />
<br />
=== On the Const applicative ===<br />
<br />
Even more straightforwardly, <hask>Const m</hask> is applicative precisely when <hask>m</hask> is a monoid.<br />
<br />
== See also ==<br />
<br />
* [http://sigfpe.blogspot.com/2009/01/haskell-monoids-and-their-uses.html Haskell Monoids and their Uses]<br />
* [http://apfelmus.nfshost.com/monoid-fingertree.html Monoids and Finger Trees]<br />
* [http://haskell.org/sitewiki/images/6/6a/TMR-Issue11.pdf Monad.Reader issue 11, "How to Refold a Map."] (PDF), and a [http://haskell.org/haskellwiki/The_Monad.Reader/Discuss_Issue11 follow up]<br />
<br />
Generalizations of monoids feature in [[Category theory]], for example:<br />
* [http://www.researchgate.net/publication/235540658_Arrows_like_Monads_are_Monoids/file/d912f511ccdf2c1016.pdf Arrows, like Monads, are Monoids] (PDF)</div>Benmachinehttps://wiki.haskell.org/index.php?title=Monoid&diff=60321Monoid2015-11-01T16:50:46Z<p>Benmachine: /* In more depth */ writer + const</p>
<hr />
<div>In Haskell, the Monoid typeclass (not to be confused with [[Monad]]) is a class for types which have a single most natural operation for combining values, together with a value which doesn't do anything when you combine it with others (this is called the ''identity'' element). It is closely related to the [[Foldable]] class, and indeed you can think of a Monoid instance declaration for a type ''m'' as precisely what you need in order to fold up a list of values of ''m''.<br />
<br />
== The basics ==<br />
<br />
=== Declaration ===<br />
<br />
<haskell><br />
class Monoid m where<br />
mempty :: m<br />
mappend :: m -> m -> m<br />
mconcat :: [m] -> m<br />
-- defining mconcat is optional, since it has the following default:<br />
mconcat = foldr mappend mempty<br />
<br />
-- this infix synonym for mappend is found in Data.Monoid<br />
x <> y = mappend x y<br />
infixr 6 <><br />
</haskell><br />
<br />
together with the following laws:<br />
<br />
<haskell><br />
-- Identity laws<br />
x <> mempty = x<br />
mempty <> x = x<br />
<br />
-- Associativity<br />
(x <> y) <> z = x <> (y <> z)<br />
</haskell><br />
<br />
=== Examples ===<br />
<br />
The prototypical and perhaps most important example is lists, which form a monoid under concatenation:<br />
<br />
<haskell><br />
instance Monoid [a] where<br />
mempty = []<br />
mappend x y = x ++ y<br />
mconcat = concat<br />
</haskell><br />
<br />
Indeed, appending the empty list to either end of an existing list does nothing, and <hask>(x ++ y) ++ z</hask> and <hask>x ++ (y ++ z)</hask> are both the same list, namely all the elements of <hask>x</hask>, then all the elements of <hask>y</hask>, them all the elements of <hask>z</hask>.<br />
<br />
Numbers also form a monoid under addition, with 0 the identity element, but they also form a monoid under multiplication, with 1 the identity element. Neither of these instances are really more natural than the other, so we use the [[newtype]]s <tt>Sum n</tt> and <tt>Product n</tt> to distinguish between them:<br />
<br />
<haskell><br />
newtype Sum n = Sum n<br />
<br />
instance Num n => Monoid (Sum n) where<br />
mempty = Sum 0<br />
mappend (Sum x) (Sum y) = Sum (x + y)<br />
<br />
newtype Product n = Product n<br />
<br />
instance Num n => Monoid (Product n) where<br />
mempty = Sum 1<br />
mappend (Sum x) (Sum y) = Sum (x * y)<br />
</haskell><br />
<br />
Now <hask>mconcat</hask> on a list of <hask>Sum Integer</hask> (say) values works like <hask>sum</hask>, while on a list of <hask>Product Double</hask> values it works like <hask>product</hask>.<br />
<br />
=== So what? ===<br />
<br />
There are several reasons why you want a typeclass for combining things, e.g. because it couples well with other typeclasses (the aforementioned [[Foldable]], or the [[Writer monad]], or some [[Applicative]]s). But for a rather striking example of what Monoid can do alone, you can look at the way its instances can work together. First, <hask>Ordering</hask>, the standard type which Haskell uses for the result of <hask>compare</hask> functions, has a "lexicographic" combination operation, where <hask>mappend</hask> essentially takes the first non-equality result. Secondly, if <hask>b</hask> is a Monoid, then functions of type <hask>a -> b</hask> can be combined by just calling them both and combining the results. Now, of course, since <hask>a -> a -> b</hask> is just a function returning a function, it can also be combined in the same way, and so you can combine comparison functions, of type <hask>a -> a -> Ordering</hask>, and write the following sorts of thing, which means "sort strings by length and then alphabetically":<br />
<br />
<haskell><br />
sortStrings = sortBy (comparing length <> compare)<br />
</haskell><br />
<br />
Isn't that wonderfully descriptive? And we didn't write any functions specifically to do this – it's just composed of simple, reusable parts.<br />
<br />
== In more depth ==<br />
<br />
=== On mconcat ===<br />
<br />
mconcat is often presented as just an optimisation, only in the class so that people can define more efficient versions of it. That's true in a sense, but note that mempty and mappend can just as well be defined in terms of mconcat:<br />
<br />
<haskell><br />
mempty = mconcat []<br />
mappend x y = mconcat [x, y]<br />
</haskell><br />
<br />
What of the laws? Well, we can have the following:<br />
<br />
<haskell><br />
mconcat [x] = x<br />
mconcat (map mconcat xss) = mconcat (concat xss)<br />
</haskell><br />
<br />
The first rule is natural enough. The second rule is a little more subtle, but basically says that if you have a list of lists of some monoidy things, and you mconcat each sublist individually, then mconcat all the results, that's just the same as if you had squashed all the sublists together first, and mconcatted the result of that. Or in other words, it's telling you something like what associativity tells you, that the order in which you fold up a list doesn't matter.<br />
<br />
==== Categorical diversion ====<br />
<br />
Note that the above two laws can also be phrased as follows:<br />
<br />
<haskell><br />
mconcat . return = id<br />
mconcat . map mconcat = mconcat . join<br />
</haskell><br />
<br />
In [[category theory]] terms, this is exactly the condition for <hask>mconcat</hask> to be a monad algebra for the list monad.<br />
<br />
=== On the Writer monad ===<br />
<br />
The [[Writer monad]] is a way to put a monad structure on tuples. You write bind like this:<br />
<br />
<haskell><br />
(w,x) >>= f =<br />
case f x of<br />
(w', y) -> (w <> w', y)<br />
</haskell><br />
<br />
Notice that it's the monoid instance of the first component that allows you to incorporate both <tt>w</tt> and <tt>w'</tt> into the final result, which seems like an important thing to do.<br />
<br />
You might, however, wonder if there's not some other way to get a law-abiding monad. The answer is essentially no: if <hask>(w,a)</hask> is a monad, you can use its monad instance to write a monoid instance for <hask>w</hask>: basically <hask>mempty = fst (return ())</hask> and <hask>mappend x y = fst (join (x,(y,()))</hask>, and the monad laws ensure associativity and identity. So in fact, monoids and monad structures on tuples are again in exact correspondence. Monoids really get around!<br />
<br />
=== On the Const applicative ===<br />
<br />
Even more straightforwardly, <hask>Const m</hask> is applicative precisely when <hask>m</hask> is a monoid.<br />
<br />
== See also ==<br />
<br />
* [http://sigfpe.blogspot.com/2009/01/haskell-monoids-and-their-uses.html Haskell Monoids and their Uses]<br />
* [http://apfelmus.nfshost.com/monoid-fingertree.html Monoids and Finger Trees]<br />
* [http://haskell.org/sitewiki/images/6/6a/TMR-Issue11.pdf Monad.Reader issue 11, "How to Refold a Map."] (PDF), and a [http://haskell.org/haskellwiki/The_Monad.Reader/Discuss_Issue11 follow up]<br />
<br />
Generalizations of monoids feature in [[Category theory]], for example:<br />
* [http://www.researchgate.net/publication/235540658_Arrows_like_Monads_are_Monoids/file/d912f511ccdf2c1016.pdf Arrows, like Monads, are Monoids] (PDF)</div>Benmachinehttps://wiki.haskell.org/index.php?title=Monoid&diff=60318Monoid2015-11-01T16:01:37Z<p>Benmachine: /* On mconcat */ cut my own unhelpful pedantry</p>
<hr />
<div>In Haskell, the Monoid typeclass (not to be confused with [[Monad]]) is a class for types which have a single most natural operation for combining values, together with a value which doesn't do anything when you combine it with others (this is called the ''identity'' element). It is closely related to the [[Foldable]] class, and indeed you can think of a Monoid instance declaration for a type ''m'' as precisely what you need in order to fold up a list of values of ''m''.<br />
<br />
== The basics ==<br />
<br />
=== Declaration ===<br />
<br />
<haskell><br />
class Monoid m where<br />
mempty :: m<br />
mappend :: m -> m -> m<br />
mconcat :: [m] -> m<br />
-- defining mconcat is optional, since it has the following default:<br />
mconcat = foldr mappend mempty<br />
<br />
-- this infix synonym for mappend is found in Data.Monoid<br />
x <> y = mappend x y<br />
infixr 6 <><br />
</haskell><br />
<br />
together with the following laws:<br />
<br />
<haskell><br />
-- Identity laws<br />
x <> mempty = x<br />
mempty <> x = x<br />
<br />
-- Associativity<br />
(x <> y) <> z = x <> (y <> z)<br />
</haskell><br />
<br />
=== Examples ===<br />
<br />
The prototypical and perhaps most important example is lists, which form a monoid under concatenation:<br />
<br />
<haskell><br />
instance Monoid [a] where<br />
mempty = []<br />
mappend x y = x ++ y<br />
mconcat = concat<br />
</haskell><br />
<br />
Indeed, appending the empty list to either end of an existing list does nothing, and <hask>(x ++ y) ++ z</hask> and <hask>x ++ (y ++ z)</hask> are both the same list, namely all the elements of <hask>x</hask>, then all the elements of <hask>y</hask>, them all the elements of <hask>z</hask>.<br />
<br />
Numbers also form a monoid under addition, with 0 the identity element, but they also form a monoid under multiplication, with 1 the identity element. Neither of these instances are really more natural than the other, so we use the [[newtype]]s <tt>Sum n</tt> and <tt>Product n</tt> to distinguish between them:<br />
<br />
<haskell><br />
newtype Sum n = Sum n<br />
<br />
instance Num n => Monoid (Sum n) where<br />
mempty = Sum 0<br />
mappend (Sum x) (Sum y) = Sum (x + y)<br />
<br />
newtype Product n = Product n<br />
<br />
instance Num n => Monoid (Product n) where<br />
mempty = Sum 1<br />
mappend (Sum x) (Sum y) = Sum (x * y)<br />
</haskell><br />
<br />
Now <hask>mconcat</hask> on a list of <hask>Sum Integer</hask> (say) values works like <hask>sum</hask>, while on a list of <hask>Product Double</hask> values it works like <hask>product</hask>.<br />
<br />
=== So what? ===<br />
<br />
There are several reasons why you want a typeclass for combining things, e.g. because it couples well with other typeclasses (the aforementioned [[Foldable]], or the [[Writer monad]], or some [[Applicative]]s). But for a rather striking example of what Monoid can do alone, you can look at the way its instances can work together. First, <hask>Ordering</hask>, the standard type which Haskell uses for the result of <hask>compare</hask> functions, has a "lexicographic" combination operation, where <hask>mappend</hask> essentially takes the first non-equality result. Secondly, if <hask>b</hask> is a Monoid, then functions of type <hask>a -> b</hask> can be combined by just calling them both and combining the results. Now, of course, since <hask>a -> a -> b</hask> is just a function returning a function, it can also be combined in the same way, and so you can combine comparison functions, of type <hask>a -> a -> Ordering</hask>, and write the following sorts of thing, which means "sort strings by length and then alphabetically":<br />
<br />
<haskell><br />
sortStrings = sortBy (comparing length <> compare)<br />
</haskell><br />
<br />
Isn't that wonderfully descriptive? And we didn't write any functions specifically to do this – it's just composed of simple, reusable parts.<br />
<br />
== In more depth ==<br />
<br />
=== On mconcat ===<br />
<br />
mconcat is often presented as just an optimisation, only in the class so that people can define more efficient versions of it. That's true in a sense, but note that mempty and mappend can just as well be defined in terms of mconcat:<br />
<br />
<haskell><br />
mempty = mconcat []<br />
mappend x y = mconcat [x, y]<br />
</haskell><br />
<br />
What of the laws? Well, we can have the following:<br />
<br />
<haskell><br />
mconcat [x] = x<br />
mconcat (map mconcat xss) = mconcat (concat xss)<br />
</haskell><br />
<br />
The first rule is natural enough. The second rule is a little more subtle, but basically says that if you have a list of lists of some monoidy things, and you mconcat each sublist individually, then mconcat all the results, that's just the same as if you had squashed all the sublists together first, and mconcatted the result of that. Or in other words, it's telling you something like what associativity tells you, that the order in which you fold up a list doesn't matter.<br />
<br />
==== Categorical diversion ====<br />
<br />
Note that the above two laws can also be phrased as follows:<br />
<br />
<haskell><br />
mconcat . return = id<br />
mconcat . map mconcat = mconcat . join<br />
</haskell><br />
<br />
In [[category theory]] terms, this is exactly the condition for <hask>mconcat</hask> to be a monad algebra for the list monad.<br />
<br />
== See also ==<br />
<br />
* [http://sigfpe.blogspot.com/2009/01/haskell-monoids-and-their-uses.html Haskell Monoids and their Uses]<br />
* [http://apfelmus.nfshost.com/monoid-fingertree.html Monoids and Finger Trees]<br />
* [http://haskell.org/sitewiki/images/6/6a/TMR-Issue11.pdf Monad.Reader issue 11, "How to Refold a Map."] (PDF), and a [http://haskell.org/haskellwiki/The_Monad.Reader/Discuss_Issue11 follow up]<br />
<br />
Generalizations of monoids feature in [[Category theory]], for example:<br />
* [http://www.researchgate.net/publication/235540658_Arrows_like_Monads_are_Monoids/file/d912f511ccdf2c1016.pdf Arrows, like Monads, are Monoids] (PDF)</div>Benmachinehttps://wiki.haskell.org/index.php?title=Monoid&diff=60317Monoid2015-11-01T15:59:10Z<p>Benmachine: mconcat stuff</p>
<hr />
<div>In Haskell, the Monoid typeclass (not to be confused with [[Monad]]) is a class for types which have a single most natural operation for combining values, together with a value which doesn't do anything when you combine it with others (this is called the ''identity'' element). It is closely related to the [[Foldable]] class, and indeed you can think of a Monoid instance declaration for a type ''m'' as precisely what you need in order to fold up a list of values of ''m''.<br />
<br />
== The basics ==<br />
<br />
=== Declaration ===<br />
<br />
<haskell><br />
class Monoid m where<br />
mempty :: m<br />
mappend :: m -> m -> m<br />
mconcat :: [m] -> m<br />
-- defining mconcat is optional, since it has the following default:<br />
mconcat = foldr mappend mempty<br />
<br />
-- this infix synonym for mappend is found in Data.Monoid<br />
x <> y = mappend x y<br />
infixr 6 <><br />
</haskell><br />
<br />
together with the following laws:<br />
<br />
<haskell><br />
-- Identity laws<br />
x <> mempty = x<br />
mempty <> x = x<br />
<br />
-- Associativity<br />
(x <> y) <> z = x <> (y <> z)<br />
</haskell><br />
<br />
=== Examples ===<br />
<br />
The prototypical and perhaps most important example is lists, which form a monoid under concatenation:<br />
<br />
<haskell><br />
instance Monoid [a] where<br />
mempty = []<br />
mappend x y = x ++ y<br />
mconcat = concat<br />
</haskell><br />
<br />
Indeed, appending the empty list to either end of an existing list does nothing, and <hask>(x ++ y) ++ z</hask> and <hask>x ++ (y ++ z)</hask> are both the same list, namely all the elements of <hask>x</hask>, then all the elements of <hask>y</hask>, them all the elements of <hask>z</hask>.<br />
<br />
Numbers also form a monoid under addition, with 0 the identity element, but they also form a monoid under multiplication, with 1 the identity element. Neither of these instances are really more natural than the other, so we use the [[newtype]]s <tt>Sum n</tt> and <tt>Product n</tt> to distinguish between them:<br />
<br />
<haskell><br />
newtype Sum n = Sum n<br />
<br />
instance Num n => Monoid (Sum n) where<br />
mempty = Sum 0<br />
mappend (Sum x) (Sum y) = Sum (x + y)<br />
<br />
newtype Product n = Product n<br />
<br />
instance Num n => Monoid (Product n) where<br />
mempty = Sum 1<br />
mappend (Sum x) (Sum y) = Sum (x * y)<br />
</haskell><br />
<br />
Now <hask>mconcat</hask> on a list of <hask>Sum Integer</hask> (say) values works like <hask>sum</hask>, while on a list of <hask>Product Double</hask> values it works like <hask>product</hask>.<br />
<br />
=== So what? ===<br />
<br />
There are several reasons why you want a typeclass for combining things, e.g. because it couples well with other typeclasses (the aforementioned [[Foldable]], or the [[Writer monad]], or some [[Applicative]]s). But for a rather striking example of what Monoid can do alone, you can look at the way its instances can work together. First, <hask>Ordering</hask>, the standard type which Haskell uses for the result of <hask>compare</hask> functions, has a "lexicographic" combination operation, where <hask>mappend</hask> essentially takes the first non-equality result. Secondly, if <hask>b</hask> is a Monoid, then functions of type <hask>a -> b</hask> can be combined by just calling them both and combining the results. Now, of course, since <hask>a -> a -> b</hask> is just a function returning a function, it can also be combined in the same way, and so you can combine comparison functions, of type <hask>a -> a -> Ordering</hask>, and write the following sorts of thing, which means "sort strings by length and then alphabetically":<br />
<br />
<haskell><br />
sortStrings = sortBy (comparing length <> compare)<br />
</haskell><br />
<br />
Isn't that wonderfully descriptive? And we didn't write any functions specifically to do this – it's just composed of simple, reusable parts.<br />
<br />
== In more depth ==<br />
<br />
=== On mconcat ===<br />
<br />
mconcat is often presented as just an optimisation, only in the class so that people can define more efficient versions of it. That's true in a sense, but note that mempty and mappend can just as well be defined in terms of mconcat:<br />
<br />
<haskell><br />
mempty = mconcat []<br />
mappend x y = mconcat [x, y]<br />
</haskell><br />
<br />
What of the laws? Well, we can have the following:<br />
<br />
<haskell><br />
mconcat [x] = x<br />
mconcat (map mconcat xss) = mconcat (concat xss)<br />
</haskell><br />
<br />
The first rule is natural enough. The second rule is a little more subtle, but basically says that if you have a list of lists of some monoidy things, and you mconcat each sublist individually, then mconcat all the results, that's just the same as if you had squashed all the sublists together first, and mconcatted the result of that. Or in other words, it's telling you something like what associativity tells you, that the order in which you fold up a list doesn't matter.<br />
<br />
The reality is a bit more subtle than that, since you need both of the laws I stated to prove associativity for mappend, and the two laws together can also prove that mempty is an identity for it. But it's a good way to think about it.<br />
<br />
==== Categorical diversion ====<br />
<br />
Note that the above two laws can also be phrased as follows:<br />
<br />
<haskell><br />
mconcat . return = id<br />
mconcat . map mconcat = mconcat . join<br />
</haskell><br />
<br />
In [[category theory]] terms, this is exactly the condition for <hask>mconcat</hask> to be a monad algebra for the list monad.<br />
<br />
== See also ==<br />
<br />
* [http://sigfpe.blogspot.com/2009/01/haskell-monoids-and-their-uses.html Haskell Monoids and their Uses]<br />
* [http://apfelmus.nfshost.com/monoid-fingertree.html Monoids and Finger Trees]<br />
* [http://haskell.org/sitewiki/images/6/6a/TMR-Issue11.pdf Monad.Reader issue 11, "How to Refold a Map."] (PDF), and a [http://haskell.org/haskellwiki/The_Monad.Reader/Discuss_Issue11 follow up]<br />
<br />
Generalizations of monoids feature in [[Category theory]], for example:<br />
* [http://www.researchgate.net/publication/235540658_Arrows_like_Monads_are_Monoids/file/d912f511ccdf2c1016.pdf Arrows, like Monads, are Monoids] (PDF)</div>Benmachinehttps://wiki.haskell.org/index.php?title=Monoid&diff=60316Monoid2015-11-01T15:01:36Z<p>Benmachine: /* See also */ cut some unnecessary stuff</p>
<hr />
<div>In Haskell, the Monoid typeclass (not to be confused with [[Monad]]) is a class for types which have a single most natural operation for combining values, together with a value which doesn't do anything when you combine it with others (this is called the ''identity'' element). It is closely related to the [[Foldable]] class, and indeed you can think of a Monoid instance declaration for a type ''m'' as precisely what you need in order to fold up a list of values of ''m''.<br />
<br />
== Declaration ==<br />
<br />
<haskell><br />
class Monoid m where<br />
mempty :: m<br />
mappend :: m -> m -> m<br />
mconcat :: [m] -> m<br />
-- defining mconcat is optional, since it has the following default:<br />
mconcat = foldr mappend mempty<br />
<br />
-- this infix synonym for mappend is found in Data.Monoid<br />
x <> y = mappend x y<br />
infixr 6 <><br />
</haskell><br />
<br />
together with the following laws:<br />
<br />
<haskell><br />
-- Identity laws<br />
x <> mempty = x<br />
mempty <> x = x<br />
<br />
-- Associativity<br />
(x <> y) <> z = x <> (y <> z)<br />
</haskell><br />
<br />
== Examples ==<br />
<br />
The prototypical and perhaps most important example is lists, which form a monoid under concatenation:<br />
<br />
<haskell><br />
instance Monoid [a] where<br />
mempty = []<br />
mappend x y = x ++ y<br />
mconcat = concat<br />
</haskell><br />
<br />
Indeed, appending the empty list to either end of an existing list does nothing, and <hask>(x ++ y) ++ z</hask> and <hask>x ++ (y ++ z)</hask> are both the same list, namely all the elements of <hask>x</hask>, then all the elements of <hask>y</hask>, them all the elements of <hask>z</hask>.<br />
<br />
Numbers also form a monoid under addition, with 0 the identity element, but they also form a monoid under multiplication, with 1 the identity element. Neither of these instances are really more natural than the other, so we use the [[newtype]]s <tt>Sum n</tt> and <tt>Product n</tt> to distinguish between them:<br />
<br />
<haskell><br />
newtype Sum n = Sum n<br />
<br />
instance Num n => Monoid (Sum n) where<br />
mempty = Sum 0<br />
mappend (Sum x) (Sum y) = Sum (x + y)<br />
<br />
newtype Product n = Product n<br />
<br />
instance Num n => Monoid (Product n) where<br />
mempty = Sum 1<br />
mappend (Sum x) (Sum y) = Sum (x * y)<br />
</haskell><br />
<br />
Now <hask>mconcat</hask> on a list of <hask>Sum Integer</hask> (say) values works like <hask>sum</hask>, while on a list of <hask>Product Double</hask> values it works like <hask>product</hask>.<br />
<br />
== So what? ==<br />
<br />
There are several reasons why you want a typeclass for combining things, e.g. because it couples well with other typeclasses (the aforementioned [[Foldable]], or the [[Writer monad]], or some [[Applicative]]s). But for a rather striking example of what Monoid can do alone, you can look at the way its instances can work together. First, <hask>Ordering</hask>, the standard type which Haskell uses for the result of <hask>compare</hask> functions, has a "lexicographic" combination operation, where <hask>mappend</hask> essentially takes the first non-equality result. Secondly, if <hask>b</hask> is a Monoid, then functions of type <hask>a -> b</hask> can be combined by just calling them both and combining the results. Now, of course, since <hask>a -> a -> b</hask> is just a function returning a function, it can also be combined in the same way, and so you can combine comparison functions, of type <hask>a -> a -> Ordering</hask>, and write the following sorts of thing, which means "sort strings by length and then alphabetically":<br />
<br />
<haskell><br />
sortStrings = sortBy (comparing length <> compare)<br />
</haskell><br />
<br />
Isn't that wonderfully descriptive? And we didn't write any functions specifically to do this – it's just composed of simple, reusable parts.<br />
<br />
== See also ==<br />
<br />
* [http://sigfpe.blogspot.com/2009/01/haskell-monoids-and-their-uses.html Haskell Monoids and their Uses]<br />
* [http://apfelmus.nfshost.com/monoid-fingertree.html Monoids and Finger Trees]<br />
* [http://haskell.org/sitewiki/images/6/6a/TMR-Issue11.pdf Monad.Reader issue 11, "How to Refold a Map."] (PDF), and a [http://haskell.org/haskellwiki/The_Monad.Reader/Discuss_Issue11 follow up]<br />
<br />
Generalizations of monoids feature in [[Category theory]], for example:<br />
* [http://www.researchgate.net/publication/235540658_Arrows_like_Monads_are_Monoids/file/d912f511ccdf2c1016.pdf Arrows, like Monads, are Monoids] (PDF)</div>Benmachinehttps://wiki.haskell.org/index.php?title=Monoid&diff=60315Monoid2015-11-01T15:00:45Z<p>Benmachine: /* So what? */ style</p>
<hr />
<div>In Haskell, the Monoid typeclass (not to be confused with [[Monad]]) is a class for types which have a single most natural operation for combining values, together with a value which doesn't do anything when you combine it with others (this is called the ''identity'' element). It is closely related to the [[Foldable]] class, and indeed you can think of a Monoid instance declaration for a type ''m'' as precisely what you need in order to fold up a list of values of ''m''.<br />
<br />
== Declaration ==<br />
<br />
<haskell><br />
class Monoid m where<br />
mempty :: m<br />
mappend :: m -> m -> m<br />
mconcat :: [m] -> m<br />
-- defining mconcat is optional, since it has the following default:<br />
mconcat = foldr mappend mempty<br />
<br />
-- this infix synonym for mappend is found in Data.Monoid<br />
x <> y = mappend x y<br />
infixr 6 <><br />
</haskell><br />
<br />
together with the following laws:<br />
<br />
<haskell><br />
-- Identity laws<br />
x <> mempty = x<br />
mempty <> x = x<br />
<br />
-- Associativity<br />
(x <> y) <> z = x <> (y <> z)<br />
</haskell><br />
<br />
== Examples ==<br />
<br />
The prototypical and perhaps most important example is lists, which form a monoid under concatenation:<br />
<br />
<haskell><br />
instance Monoid [a] where<br />
mempty = []<br />
mappend x y = x ++ y<br />
mconcat = concat<br />
</haskell><br />
<br />
Indeed, appending the empty list to either end of an existing list does nothing, and <hask>(x ++ y) ++ z</hask> and <hask>x ++ (y ++ z)</hask> are both the same list, namely all the elements of <hask>x</hask>, then all the elements of <hask>y</hask>, them all the elements of <hask>z</hask>.<br />
<br />
Numbers also form a monoid under addition, with 0 the identity element, but they also form a monoid under multiplication, with 1 the identity element. Neither of these instances are really more natural than the other, so we use the [[newtype]]s <tt>Sum n</tt> and <tt>Product n</tt> to distinguish between them:<br />
<br />
<haskell><br />
newtype Sum n = Sum n<br />
<br />
instance Num n => Monoid (Sum n) where<br />
mempty = Sum 0<br />
mappend (Sum x) (Sum y) = Sum (x + y)<br />
<br />
newtype Product n = Product n<br />
<br />
instance Num n => Monoid (Product n) where<br />
mempty = Sum 1<br />
mappend (Sum x) (Sum y) = Sum (x * y)<br />
</haskell><br />
<br />
Now <hask>mconcat</hask> on a list of <hask>Sum Integer</hask> (say) values works like <hask>sum</hask>, while on a list of <hask>Product Double</hask> values it works like <hask>product</hask>.<br />
<br />
== So what? ==<br />
<br />
There are several reasons why you want a typeclass for combining things, e.g. because it couples well with other typeclasses (the aforementioned [[Foldable]], or the [[Writer monad]], or some [[Applicative]]s). But for a rather striking example of what Monoid can do alone, you can look at the way its instances can work together. First, <hask>Ordering</hask>, the standard type which Haskell uses for the result of <hask>compare</hask> functions, has a "lexicographic" combination operation, where <hask>mappend</hask> essentially takes the first non-equality result. Secondly, if <hask>b</hask> is a Monoid, then functions of type <hask>a -> b</hask> can be combined by just calling them both and combining the results. Now, of course, since <hask>a -> a -> b</hask> is just a function returning a function, it can also be combined in the same way, and so you can combine comparison functions, of type <hask>a -> a -> Ordering</hask>, and write the following sorts of thing, which means "sort strings by length and then alphabetically":<br />
<br />
<haskell><br />
sortStrings = sortBy (comparing length <> compare)<br />
</haskell><br />
<br />
Isn't that wonderfully descriptive? And we didn't write any functions specifically to do this – it's just composed of simple, reusable parts.<br />
<br />
== See also ==<br />
<br />
The monoid interface enables a number of algorithms, including parallel algorithms and tree searches, e.g.:<br />
* An introduction: [http://sigfpe.blogspot.com/2009/01/haskell-monoids-and-their-uses.html Haskell Monoids and their Uses]<br />
* The blog article [http://apfelmus.nfshost.com/monoid-fingertree.html Monoids and Finger Trees]<br />
* [http://haskell.org/sitewiki/images/6/6a/TMR-Issue11.pdf Monad.Reader issue 11, "How to Refold a Map."] (PDF), and a [http://haskell.org/haskellwiki/The_Monad.Reader/Discuss_Issue11 follow up]<br />
<br />
Generalizations of monoids feature in [[Category theory]], for example:<br />
* [http://www.researchgate.net/publication/235540658_Arrows_like_Monads_are_Monoids/file/d912f511ccdf2c1016.pdf Arrows, like Monads, are Monoids] (PDF)</div>Benmachinehttps://wiki.haskell.org/index.php?title=Newtype&diff=60314Newtype2015-11-01T14:59:47Z<p>Benmachine: syntax highlighting is getting single quotes wrong</p>
<hr />
<div>A <hask>newtype</hask> declaration creates a new type in much the same way as <hask>data</hask>. The syntax and usage of newtypes is virtually identical to that of data declarations - in fact, you can replace the <hask>newtype</hask> keyword with <hask>data</hask> and it'll still compile, indeed there's even a good chance your program will still work. The converse is not true, however - <hask>data</hask> can only be replaced with <hask>newtype</hask> if the type has ''exactly one constructor'' with ''exactly one field'' inside it.<br />
<br />
Some examples:<br />
<br />
<haskell><br />
newtype Fd = Fd CInt<br />
-- data Fd = Fd CInt would also be valid<br />
<br />
-- newtypes can have deriving clauses just like normal types<br />
newtype Identity a = Identity a<br />
deriving (Eq, Ord, Read, Show)<br />
<br />
-- record syntax is still allowed, but only for one field<br />
newtype State s a = State { runState :: s -> (s, a) }<br />
<br />
-- this is *not* allowed:<br />
-- newtype Pair a b = Pair { pairFst :: a, pairSnd :: b }<br />
-- but this is:<br />
data Pair a b = Pair { pairFst :: a, pairSnd :: b }<br />
-- and so is this:<br />
newtype NPair a b = NPair (a, b)<br />
</haskell><br />
<br />
Sounds pretty limited! So why does anyone use <hask>newtype</hask>?<br />
<br />
== The short version ==<br />
<br />
The restriction to one constructor with one field means that the new type and the type of the field are in direct correspondence:<br />
<br />
<haskell><br />
State :: (s -> (s, a)) -> State s a<br />
runState :: State s a -> (s -> (s, a))<br />
</haskell><br />
<br />
or in mathematical terms they are ''isomorphic''. This means that after the type is checked at compile time, at run time the two types can be treated essentially the same, without the overhead or indirection normally associated with a data constructor. So if you want to declare different type class instances for a particular type, or want to make a type abstract, you can wrap it in a <hask>newtype</hask> and it'll be considered distinct to the type-checker, but identical at runtime. You can then use all sorts of deep trickery like phantom or recursive types without worrying about GHC shuffling buckets of bytes for no reason.<br />
<br />
== The messy bits ==<br />
<br />
Why doesn't everyone just use <hask>newtype</hask> whenever they can, then? Well, quite often they do. But there is a subtle yet semantically significant difference. When we create a data type supposedly isomorphic to <hask>Bool</hask> like so:<br />
<br />
<haskell>data Any = Any { getAny :: Bool }</haskell><br />
<br />
we actually find that the isomorphism isn't exact:<br />
<br />
<haskell><br />
Any . getAny $ Any True = Any True -- okay, fine<br />
Any . getAny $ Any False = Any False -- also fine<br />
Any . getAny $ Any ⊥ = Any ⊥ -- so far so good<br />
Any . getAny $ ⊥ = Any ⊥ -- wait a second...<br />
</haskell><br />
([[Bottom|what's that upside-down T thing?]])<br />
<br />
The problem is that types declared with the <hask>data</hask> keyword are ''lifted'' - that is, they contain their own ⊥ value that is distinct from all the others. In this example, we have <hask>⊥ :: Any</hask> distinct from <hask>Any ⊥ :: Any</hask>. What this means is that the following pattern match:<br />
<br />
<haskell><br />
case x of<br />
Any _ -> ()<br />
</haskell><br />
<br />
must evaluate its argument, even though it seems like the pattern match can't fail: we must check whether <hask>x</hask> is <hask>⊥</hask> or <hask>Any y</hask> for some <hask>y</hask>.<br />
<br />
This is intrinsic to Haskell's lazy, non-total semantics. The problem is that this means tracking whether a value is wrapped in a constructor or not, which means keeping track of those extra constructors at runtime even when all they do is distinguish an extra bottom value we don't even want. So in order to be consistent, but also allow the exact isomorphism to be preserved, Haskell provides the <hask>newtype</hask> keyword, for the construction of unlifted types. Pattern-matching on a newtype constructor doesn't do any work, because there is no separate ⊥ so every value in the type is wrapped in the constructor.<br />
<br />
== What about strict types? ==<br />
<br />
You may notice that a type like<br />
<br />
<haskell>data Identity' a = Identity' !a</haskell><br />
<br />
has <hask>Identity' ⊥ = ⊥</hask> and so you might think you have your coveted isomorphism. But all the strictness annotation means is that <hask>Identity' ⊥</hask> really means <hask>Identity' $! ⊥</hask> - the semantics of the type are fundamentally the same, and in particular the case expression still forces the value.<br />
<br />
== Examples ==<br />
<br />
<haskell><br />
module Foo where<br />
<br />
data Foo1 = Foo1 Int -- Defines Foo1 constructor that lazily refers to an Int<br />
data Foo2 = Foo2 !Int -- Defines Foo2 constructor that strictly refers to an Int<br />
newtype Foo3 = Foo3 Int -- Defines Foo3 constructor that is synonymous with Int<br />
<br />
-- Argument is lazy and ignored, so <br />
-- undefined does not cause failure since<br />
-- the contructor pattern match succeeds.<br />
x1 = case Foo1 undefined of<br />
Foo1 _ -> 1 -- 1<br />
<br />
-- Argument is strict (because of !), so<br />
-- undefined does cause failure.<br />
x2 = case Foo2 undefined of<br />
Foo2 _ -> 1 -- undefined<br />
<br />
-- The newtype behaves like Int, see yInt below<br />
x3 = case Foo3 undefined of<br />
Foo3 _ -> 1 -- 1<br />
<br />
-- Constructor pattern match fails<br />
y1 = case undefined of<br />
Foo1 _ -> 1 -- undefined<br />
<br />
-- Constructor pattern match fails<br />
y2 = case undefined of<br />
Foo2 _ -> 1 -- undefined<br />
<br />
-- The newtype behaves like Int, there is no<br />
-- constructor at runtime.<br />
y3 = case undefined of<br />
Foo3 _ -> 1 -- 1<br />
<br />
-- Demonstration of Int behavior<br />
int :: Int<br />
int = undefined<br />
<br />
yInt = case int of<br />
_ -> 1 -- 1<br />
</haskell><br />
<br />
== See also ==<br />
<br />
The Haskell 98 Report defines newtypes in [http://www.haskell.org/onlinereport/decls.html#sect4.2.3 section 4.2.3].<br />
<br />
[[Category:FAQ]]<br />
[[Category:Language]]</div>Benmachinehttps://wiki.haskell.org/index.php?title=Monoid&diff=60313Monoid2015-11-01T14:23:38Z<p>Benmachine: /* Declaration */ fixity of <></p>
<hr />
<div>In Haskell, the Monoid typeclass (not to be confused with [[Monad]]) is a class for types which have a single most natural operation for combining values, together with a value which doesn't do anything when you combine it with others (this is called the ''identity'' element). It is closely related to the [[Foldable]] class, and indeed you can think of a Monoid instance declaration for a type ''m'' as precisely what you need in order to fold up a list of values of ''m''.<br />
<br />
== Declaration ==<br />
<br />
<haskell><br />
class Monoid m where<br />
mempty :: m<br />
mappend :: m -> m -> m<br />
mconcat :: [m] -> m<br />
-- defining mconcat is optional, since it has the following default:<br />
mconcat = foldr mappend mempty<br />
<br />
-- this infix synonym for mappend is found in Data.Monoid<br />
x <> y = mappend x y<br />
infixr 6 <><br />
</haskell><br />
<br />
together with the following laws:<br />
<br />
<haskell><br />
-- Identity laws<br />
x <> mempty = x<br />
mempty <> x = x<br />
<br />
-- Associativity<br />
(x <> y) <> z = x <> (y <> z)<br />
</haskell><br />
<br />
== Examples ==<br />
<br />
The prototypical and perhaps most important example is lists, which form a monoid under concatenation:<br />
<br />
<haskell><br />
instance Monoid [a] where<br />
mempty = []<br />
mappend x y = x ++ y<br />
mconcat = concat<br />
</haskell><br />
<br />
Indeed, appending the empty list to either end of an existing list does nothing, and <hask>(x ++ y) ++ z</hask> and <hask>x ++ (y ++ z)</hask> are both the same list, namely all the elements of <hask>x</hask>, then all the elements of <hask>y</hask>, them all the elements of <hask>z</hask>.<br />
<br />
Numbers also form a monoid under addition, with 0 the identity element, but they also form a monoid under multiplication, with 1 the identity element. Neither of these instances are really more natural than the other, so we use the [[newtype]]s <tt>Sum n</tt> and <tt>Product n</tt> to distinguish between them:<br />
<br />
<haskell><br />
newtype Sum n = Sum n<br />
<br />
instance Num n => Monoid (Sum n) where<br />
mempty = Sum 0<br />
mappend (Sum x) (Sum y) = Sum (x + y)<br />
<br />
newtype Product n = Product n<br />
<br />
instance Num n => Monoid (Product n) where<br />
mempty = Sum 1<br />
mappend (Sum x) (Sum y) = Sum (x * y)<br />
</haskell><br />
<br />
Now <hask>mconcat</hask> on a list of <hask>Sum Integer</hask> (say) values works like <hask>sum</hask>, while on a list of <hask>Product Double</hask> values it works like <hask>product</hask>.<br />
<br />
== So what? ==<br />
<br />
There are several reasons why you want a typeclass for combining things, e.g. because it couples well with other typeclasses (the aforementioned [[Foldable]], or the [[Writer monad]], or some [[Applicative]]s). But for a rather striking example of what Monoid can do alone, you can look at the way its instances can work together. First, <hask>Ordering</hask>, the standard type which Haskell uses for the result of <hask>compare</hask> functions, has a "lexicographic" combination operation, where <hask>mappend</hask> essentially takes the first non-equality result. Secondly, if <hask>b</hask> is a Monoid, then functions of type <hask>a -> b</hask> can be combined by just calling them both and combining the results. Now, of course, since <hask>a -> a -> b</hask> is just a function returning a function, it can also be combined in the same way. And so you can combine comparison functions, of type <hask>a -> a -> Ordering</hask>, and write the following sorts of thing, which means "sort strings by length and then alphabetically":<br />
<br />
<haskell><br />
sortStrings = sortBy (comparing length <> compare)<br />
</haskell><br />
<br />
Isn't that wonderfully descriptive? And we didn't write any functions specifically to do this – it's just composed of simple, reusable parts.<br />
<br />
== See also ==<br />
<br />
The monoid interface enables a number of algorithms, including parallel algorithms and tree searches, e.g.:<br />
* An introduction: [http://sigfpe.blogspot.com/2009/01/haskell-monoids-and-their-uses.html Haskell Monoids and their Uses]<br />
* The blog article [http://apfelmus.nfshost.com/monoid-fingertree.html Monoids and Finger Trees]<br />
* [http://haskell.org/sitewiki/images/6/6a/TMR-Issue11.pdf Monad.Reader issue 11, "How to Refold a Map."] (PDF), and a [http://haskell.org/haskellwiki/The_Monad.Reader/Discuss_Issue11 follow up]<br />
<br />
Generalizations of monoids feature in [[Category theory]], for example:<br />
* [http://www.researchgate.net/publication/235540658_Arrows_like_Monads_are_Monoids/file/d912f511ccdf2c1016.pdf Arrows, like Monads, are Monoids] (PDF)</div>Benmachinehttps://wiki.haskell.org/index.php?title=Monoid&diff=60312Monoid2015-11-01T14:22:13Z<p>Benmachine: rewrite</p>
<hr />
<div>In Haskell, the Monoid typeclass (not to be confused with [[Monad]]) is a class for types which have a single most natural operation for combining values, together with a value which doesn't do anything when you combine it with others (this is called the ''identity'' element). It is closely related to the [[Foldable]] class, and indeed you can think of a Monoid instance declaration for a type ''m'' as precisely what you need in order to fold up a list of values of ''m''.<br />
<br />
== Declaration ==<br />
<br />
<haskell><br />
class Monoid m where<br />
mempty :: m<br />
mappend :: m -> m -> m<br />
mconcat :: [m] -> m<br />
-- defining mconcat is optional, since it has the following default:<br />
mconcat = foldr mappend mempty<br />
<br />
-- this infix synonym for mappend is also useful<br />
x <> y = mappend x y<br />
</haskell><br />
<br />
together with the following laws:<br />
<br />
<haskell><br />
-- Identity laws<br />
x <> mempty = x<br />
mempty <> x = x<br />
<br />
-- Associativity<br />
(x <> y) <> z = x <> (y <> z)<br />
</haskell><br />
<br />
== Examples ==<br />
<br />
The prototypical and perhaps most important example is lists, which form a monoid under concatenation:<br />
<br />
<haskell><br />
instance Monoid [a] where<br />
mempty = []<br />
mappend x y = x ++ y<br />
mconcat = concat<br />
</haskell><br />
<br />
Indeed, appending the empty list to either end of an existing list does nothing, and <hask>(x ++ y) ++ z</hask> and <hask>x ++ (y ++ z)</hask> are both the same list, namely all the elements of <hask>x</hask>, then all the elements of <hask>y</hask>, them all the elements of <hask>z</hask>.<br />
<br />
Numbers also form a monoid under addition, with 0 the identity element, but they also form a monoid under multiplication, with 1 the identity element. Neither of these instances are really more natural than the other, so we use the [[newtype]]s <tt>Sum n</tt> and <tt>Product n</tt> to distinguish between them:<br />
<br />
<haskell><br />
newtype Sum n = Sum n<br />
<br />
instance Num n => Monoid (Sum n) where<br />
mempty = Sum 0<br />
mappend (Sum x) (Sum y) = Sum (x + y)<br />
<br />
newtype Product n = Product n<br />
<br />
instance Num n => Monoid (Product n) where<br />
mempty = Sum 1<br />
mappend (Sum x) (Sum y) = Sum (x * y)<br />
</haskell><br />
<br />
Now <hask>mconcat</hask> on a list of <hask>Sum Integer</hask> (say) values works like <hask>sum</hask>, while on a list of <hask>Product Double</hask> values it works like <hask>product</hask>.<br />
<br />
== So what? ==<br />
<br />
There are several reasons why you want a typeclass for combining things, e.g. because it couples well with other typeclasses (the aforementioned [[Foldable]], or the [[Writer monad]], or some [[Applicative]]s). But for a rather striking example of what Monoid can do alone, you can look at the way its instances can work together. First, <hask>Ordering</hask>, the standard type which Haskell uses for the result of <hask>compare</hask> functions, has a "lexicographic" combination operation, where <hask>mappend</hask> essentially takes the first non-equality result. Secondly, if <hask>b</hask> is a Monoid, then functions of type <hask>a -> b</hask> can be combined by just calling them both and combining the results. Now, of course, since <hask>a -> a -> b</hask> is just a function returning a function, it can also be combined in the same way. And so you can combine comparison functions, of type <hask>a -> a -> Ordering</hask>, and write the following sorts of thing, which means "sort strings by length and then alphabetically":<br />
<br />
<haskell><br />
sortStrings = sortBy (comparing length <> compare)<br />
</haskell><br />
<br />
Isn't that wonderfully descriptive? And we didn't write any functions specifically to do this – it's just composed of simple, reusable parts.<br />
<br />
== See also ==<br />
<br />
The monoid interface enables a number of algorithms, including parallel algorithms and tree searches, e.g.:<br />
* An introduction: [http://sigfpe.blogspot.com/2009/01/haskell-monoids-and-their-uses.html Haskell Monoids and their Uses]<br />
* The blog article [http://apfelmus.nfshost.com/monoid-fingertree.html Monoids and Finger Trees]<br />
* [http://haskell.org/sitewiki/images/6/6a/TMR-Issue11.pdf Monad.Reader issue 11, "How to Refold a Map."] (PDF), and a [http://haskell.org/haskellwiki/The_Monad.Reader/Discuss_Issue11 follow up]<br />
<br />
Generalizations of monoids feature in [[Category theory]], for example:<br />
* [http://www.researchgate.net/publication/235540658_Arrows_like_Monads_are_Monoids/file/d912f511ccdf2c1016.pdf Arrows, like Monads, are Monoids] (PDF)</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine/hasktag_bug&diff=60311User:Benmachine/hasktag bug2015-11-01T12:45:49Z<p>Benmachine: deleting exposition of now-fixed bug</p>
<hr />
<div>One of these was fixed, but this one still remains:<br />
<br />
=== Paragraphs ===<br />
<br />
Use of the tag seems to merge consecutive paragraphs:<br />
<br />
Here is a paragraph with <hask>code</hask> in it.<br />
<br />
Here is another, distinct paragraph, with more <hask>code</hask> in it.<br />
<br />
Here is a paragraph with no code.</div>Benmachinehttps://wiki.haskell.org/index.php?title=Polymorphism&diff=59216Polymorphism2015-01-21T00:50:09Z<p>Benmachine: </p>
<hr />
<div>[[Category:Glossary]]<br />
A value is polymorphic if there is more than one type it can have. Polymorphism is widespread in Haskell and is a key feature of its type system.<br />
<br />
Most polymorphism in Haskell falls into one of two broad categories: [[#Parametric polymorphism|''parametric'']] polymorphism and [[#Ad-hoc polymorphism|''ad-hoc'']] polymorphism.<br />
<br />
=== Parametric polymorphism ===<br />
<br />
Parametric polymorphism refers to when the type of a value contains one or more (unconstrained) ''type variables'', so that the value may adopt any type that results from substituting those variables with concrete types.<br />
<br />
In Haskell, this means any type in which a type variable, denoted by a name in a type beginning with a lowercase letter, appears without constraints (i.e. does not appear to the left of a <tt>=></tt>). In Java and some similar languages, generics (roughly speaking) fill this role.<br />
<br />
For example, the function <hask>id :: a -> a</hask> contains an unconstrained type variable <hask>a</hask> in its type, and so can be used in a context requiring <hask>Char -> Char</hask> or <hask>Integer -> Integer</hask> or <hask>(Bool -> Maybe Bool) -> (Bool -> Maybe Bool)</hask> or any of a literally infinite list of other possibilities. Likewise, the empty list <hask>[] :: [a]</hask> belongs to every list type, and the polymorphic function <hask>map :: (a -> b) -> [a] -> [b]</hask> may operate on any function type. Note, however, that if a single type variable appears multiple times, it must take the same type everywhere it appears, so e.g. the result type of <hask>id</hask> must be the same as the argument type, and the input and output types of the function given to <hask>map</hask> must match up with the list types.<br />
<br />
Since a parametrically polymorphic value does not "know" anything about the unconstrained type variables, it must behave the same regardless of its type. This is a somewhat limiting but extremely useful property known as [[parametricity]].<br />
<br />
=== Ad-hoc polymorphism ===<br />
<br />
Ad-hoc polymorphism refers to when a value is able to adopt any one of several types because it, or a value it uses, has been given a separate definition for each of those types. For example, the <tt>+</tt> operator essentially does something entirely different when applied to floating-point values as compared to when applied to integers – in Python it can even be applied to strings as well. Most languages support at least some ad-hoc polymorphism, but in languages like C it is restricted to only built-in functions and types. Other languages like C++ allow programmers to provide their own overloading, supplying multiple definitions of a single function, to be disambiguated by the types of the arguments. In Haskell, this is achieved via the system of [[type class]]es and class instances.<br />
<br />
Despite the similarity of the name, Haskell's type classes are quite different from the classes of most object-oriented languages. They have more in common with interfaces, in that they specify a series of methods or values by their type signature, to be implemented by an instance declaration.<br />
<br />
So, for example, if my type can be compared for equality (most types can, but some, particularly function types, cannot) then I can give an instance declaration of the <hask>Eq</hask> class. All I have to do is specify the behaviour of the <hask>==</hask> operator on my type, and I gain the ability to use all sorts of functions defined using that operator, e.g. checking if a value of my type is present in a list, or looking up a corresponding value in a list of pairs.<br />
<br />
Unlike the overloading in some languages, overloading in Haskell is not limited to functions – <tt>minBound</tt> is an example of an overloaded ''value'', so that when used as a <tt>Char</tt> it will have value <tt>'\NUL'</tt> while as an <tt>Int</tt> it might be <tt>-2147483648</tt>.<br />
<br />
Haskell even allows class instances to be defined for types which are themselves polymorphic (either ad-hoc or parametrically). So for example, an instance can be defined of <tt>Eq</tt> that says "if <tt>a</tt> has an equality operation, then <tt>[a]</tt> has one". Then, of course, <tt><nowiki>[[a]]</nowiki></tt> will automatically also have an instance, and so complex compound types can have instances built for them out of the instances of their components.<br />
<br />
You can recognise the presence of ad-hoc polymorphism by looking for ''constrained'' type variables: that is, variables that appear to the left of <hask>=></hask>, like in <hask>elem :: (Eq a) => a -> [a] -> Bool</hask>. Note that <hask>lookup :: (Eq a) => a -> [(a,b)] -> Maybe b</hask> exhibits both parametric (in <hask>b</hask>) and ad-hoc (in <hask>a</hask>) polymorphism.<br />
<br />
=== Other kinds of polymorphism ===<br />
<br />
There are several more exotic flavours of polymorphism that are implemented in some extensions to Haskell, e.g. [[rank-N types]] and [[impredicative types]].<br />
<br />
There are some kinds of polymorphism that Haskell doesn't support, or at least not natively, e.g. inclusion polymorphism and subtyping, common in OO languages, where values of one type can act as values of another type.<br />
<br />
== Further reading ==<br />
*[http://lucacardelli.name/Papers/OnUnderstanding.A4.pdf On Understanding Types, Data Abstraction, and Polymorphism (1985)], by Luca Cardelli, Peter Wegner in ACM Computing Surveys.<br />
<br />
*[http://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf On Understanding Data Abstraction, Revisited (2009)], by William R. Cook in OOPSLA 2009.<br />
<br />
*[http://en.wikipedia.org/wiki/Type_polymorphism Type polymorphism] at Wikipedia</div>Benmachinehttps://wiki.haskell.org/index.php?title=Seq&diff=59016Seq2014-10-19T15:25:09Z<p>Benmachine: </p>
<hr />
<div><span>{{DISPLAYTITLE:seq}}</span><br />
<br />
The <tt>seq</tt> function is the most basic method of introducing strictness to a Haskell program. <tt>seq :: a -> b -> b</tt> takes two arguments of any type, and returns the second. However, it also has the important property that it is magically strict in its first argument. In essence, <tt>seq</tt> is defined by the following two equations:<br />
<br />
<haskell><br />
⊥ `seq` b = ⊥<br />
a `seq` b = b<br />
</haskell><br />
<br />
See [[Bottom]] for an explanation of the ⊥ symbol.<br />
<br />
A common misconception regarding <tt>seq</tt> is that <tt>seq x</tt> "evaluates" <tt>x</tt>. Well, sort of. <tt>seq</tt> doesn't evaluate anything just by virtue of existing in the source file, all it does is introduce an artificial data dependency of one value on another: when the result of <tt>seq</tt> is evaluated, the first argument must also (sort of; see below) be evaluated. As an example, suppose <tt>x :: Integer</tt>, then <tt>seq x b</tt> behaves essentially like <tt>if x == 0 then b else b</tt> – unconditionally equal to <tt>b</tt>, but forcing <tt>x</tt> along the way. In particular, the expression <tt>x `seq` x</tt> is completely redundant, and always has exactly the same effect as just writing <tt>x</tt>.<br />
<br />
Strictly speaking, the two equations of <tt>seq</tt> are all it must satisfy, and if the compiler can statically prove that the first argument is not ⊥, or that its second argument ''is'', it doesn't have to evaluate anything to meet its obligations. In practice, this almost never happens, and would probably be considered highly counterintuitive behaviour on the part of GHC (or whatever else you use to run your code). However, it ''is'' the case that evaluating <tt>b</tt> and ''then'' <tt>a</tt>, then returning <tt>b</tt> is a perfectly legitimate thing to do; it was to prevent this ambiguity that <tt>pseq</tt> was invented, but that's another story.<br />
<br />
=== Common uses of <tt>seq</tt> ===<br />
<br />
<tt>seq</tt> is typically used in the semantic interpretation of other strictness techniques, like strictness annotations in data types, or GHC's <tt>BangPatterns</tt> extension. For example, the meaning of this:<br />
<br />
<haskell><br />
f !x !y = z<br />
</haskell><br />
<br />
is this:<br />
<br />
<haskell><br />
f x y | x `seq` y `seq` False = undefined<br />
| otherwise = z<br />
</haskell><br />
<br />
although that literal translation may not actually take place.<br />
<br />
<tt>seq</tt> is frequently used with accumulating parameters to ensure that they don't become huge thunks, which will be forced at the end anyway. For example, strict foldl:<br />
<br />
<haskell><br />
foldl' :: (a -> b -> a) -> a -> [b] -> a<br />
foldl' _ z [] = z<br />
foldl' f z (x:xs) = let z' = f z x in z' `seq` foldl' f z' xs<br />
</haskell><br />
<br />
It's also used to define strict application:<br />
<br />
<haskell><br />
($!) :: (a -> b) -> a -> b<br />
f $! x = x `seq` f x<br />
</haskell><br />
<br />
which is useful for some of the same reasons.<br />
<br />
=== Controversy! ===<br />
<br />
Note that <tt>seq</tt> is the ''only'' way to force evaluation of a value with a function type (except by applying it, which is liable to cause other problems). As such, it is the only reason why Haskell programs are able to distinguish between the following two values:<br />
<br />
<haskell><br />
undefined :: a -> b<br />
const undefined :: a -> b<br />
</haskell><br />
<br />
This violates the principle from lambda calculus of extensionality of functions, or eta-conversion, because <tt>f</tt> and <tt>\x -> f x</tt> are distinct functions, even though they return the same output for ''every'' input. For this reason, <tt>seq</tt>, and this distinction, is sometimes ignored e.g. when assessing the correctness of [[Correctness of short cut fusion|optimisation techniques]] or type class instances.<br />
<br />
== See also ==<br />
<br />
* [http://stackoverflow.com/questions/12687392/why-is-seq-bad Why is seq bad?]<br />
<br />
[[Category:Glossary]]</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine/Overqualified_modules&diff=59015User:Benmachine/Overqualified modules2014-10-19T15:22:01Z<p>Benmachine: italicising</p>
<hr />
<div>== Overqualified modules ==<br />
<br />
The hierarchical module system was originally proposed as an extension to the Haskell98 standard, and adopted formally in Haskell2010. It is typically regarded as one of the less controversial extensions, because more or less everyone agreed that single-token module names were liable to become a huge tangled mess with everyone stepping on each others' toes.<br />
<br />
=== Data.Data.Data ===<br />
<br />
I lack a little historical context here, since the extension was widespread before I was introduced to Haskell, but I think that the current layout of the module hierarchy is unsatisfactory. Having been given hierarchical modules, Haskellers seem to feel obliged to use them: single-component names are virtually unheard of. Yet in many cases, the additional categorisation seems to add no semantic content whatsoever. What do we learn about a module by its name <tt>Data.Bool</tt> that was not already evident in the <tt>Bool</tt>? Why is the <tt>Functor</tt> type class a piece of <tt>Data</tt> but the closely-related <tt>Applicative</tt> type class a <tt>Control</tt> structure? Why do we have <tt>Data.Monoid</tt> but <tt>Control.Category</tt>?<br />
<br />
=== Redundant specification ===<br />
<br />
There are certainly cases where the additional qualification adds meaning. Writing <hask>import Haskell</hask> at the top of your file seems meaningless, where in <hask>import Haskell.Parser</hask> you have a slightly better idea of what is being requested. However, minimalism is desirable: when adding a component to your module name, ask yourself if it resolves any confusion or prevents any ambiguity. I would argue that in <tt>Codec.Binary.UTF8.Generic</tt>, for example, nearly all of the name is redundant. There is no UTF-8 that is not a binary codec, and arguably the <tt>Generic</tt> component of the name is equally unenlightening. Just name the module <tt>UTF8</tt>, the shortest unambiguous description of its purpose.<br />
<br />
=== Redundant disambiguation ===<br />
<br />
One could argue that keeping module names long reduces the risk of collision. It's true that specifying more information in the module name might reduce the chance of some other module clashing with it, but often people confuse “information content” with “textual length”: clearly, grouping all monad-related modules under <tt>Control.Monad</tt> instead of just <tt>Monad</tt> is not going to stop two implementations of <tt>Reader</tt> from interfering with each other. So keep just the meaningful component of the name: what, after all, could possibly be named <tt>Monad</tt> except for a module housing the <tt>Monad</tt> class and related utility functions? Likewise <tt>Applicative</tt>, <tt>List</tt>, <tt>Exception</tt>, <tt>IO</tt>: all sorts of concepts are clearly going to exist only once in Haskell. Those that don't are no better served being <tt>Control.Monad.Reader</tt> than <tt>Monad.Reader</tt>.<br />
<br />
If you really want to avoid name collisions, take a leaf from syb's book: previously under the hierarchy <tt>Data.Generics</tt>, which not only suffered from <tt>Data</tt>-itis but also adequately described any generic programming mechanism, syb is starting to move over to the new, more specific <tt>Generics.SYB</tt> hierarchy. This drops the useless <tt>Data</tt> prefix and instead uses a component – the name of the package – that is very likely to be unique to this particular design and implementation. We appear to lose some "generality", but in reality the knowledge that you were using SYB in particular was probably already encoded in your program, since other generics libraries will have made different design decisions. The new name also emphasises the position of syb as ''a'' generics library, not ''the'' generics library – on an equal footing with Uniplate and other similar tools.<br />
<br />
=== Internal package politics ===<br />
<br />
Hierarchical modules do make internal structuring of a project easier; one only needs to look at something like Haskore's module list to see that they could clearly not just all be dumped in a single source directory. So that is a legitimate use, but of course there's not necessarily any reason why the internal structure of your project has to be reflected in the external API you provide. If you want twenty helper modules in various tidy subdirectories, fine, but you can probably re-export everything relevant (and it is good design not to export too much) in just a few root modules at the base of your hierarchy. Don't confuse what makes life easy for the library author with what makes things easy for the library user – and don't assume you need to trade one off against the other.<br />
<br />
=== Some syntactical digressions ===<br />
<br />
In addition to the above practical concerns, I also somewhat object to the overuse of the poor little <hask>.</hask> character. For example, one should in principle be able to write a list of all weekdays as <hask>[Monday..]</hask>, but this actually parses as a qualified reference to the Monday module – you'll need to use the marginally uglier <hask>[Monday ..]</hask>. This also demonstrates how the syntax for qualified operators is just plain ugly. It's hard to write and equally hard to read <hask>7 Prelude.+ 8</hask> or, to really rub it in, <hask>f Control.Category.. g</hask>.<br />
<br />
== Conclusion ==<br />
<br />
Hierarchical modules added some much-needed structure to Haskell's module namespace, but should be used sparingly and responsibly to avoid tragic keyboard wear every time I want to <hask>import qualified Text.ParserCombinators.Parsec.Combinator as PCPC</hask>. The policy on how best to name your modules has historically been loose, and the coherence of the module landscape has suffered for it.<br />
<br />
== See also ==<br />
<br />
* [http://www.reddit.com/r/haskell/comments/zdev6/hierarchical_modules_are_frequently_misused/ This article linked on reddit]</div>Benmachinehttps://wiki.haskell.org/index.php?title=Strings&diff=57635Strings2014-03-02T20:38:45Z<p>Benmachine: </p>
<hr />
<div>{{Stub}}<br />
<br />
There are several types of strings that can be used in Haskell programs.<br />
<br />
== String ==<br />
<br />
<hask>String</hask> is the only string type mandated by the language standard, and as such is overwhelmingly the most common, especially for non-performance-sensitive applications. It is simply a type synonym for <hask>[Char]</hask>.<br />
<br />
Pros:<br />
* conceptually simple and easy to use<br />
* interfaces well with other list functions<br />
<br />
Cons:<br />
* massive overhead, up to 4 words per character, which also has speed implications<br />
* not pedantically Unicode-correct in some cases (e.g. there are strings which change length when changing case, so <hask>map toLower</hask> is not accurate in that case)<br />
<br />
== ByteString ==<br />
<br />
<hask>ByteString</hask> is a type defined in the package [http://hackage.haskell.org/package/bytestring bytestring], available from Hackage.<br />
<br />
Bytestrings are sequences of ''bytes'' not characters, and aren't really a text type at all. They are best used for binary data.<br />
<br />
They are low-overhead in space terms and very heavily optimised – they are a key part of writing high-performance code in Haskell.<br />
<br />
=== Data.ByteString.Char8 ===<br />
<br />
TODO<br />
<br />
== Text ==<br />
<br />
For a more efficient processing of text, there is <hask>Text</hask>, defined in the package [http://hackage.haskell.org/package/text text].<br />
<br />
There are two version of <hask>Text</hask>s: lazy and strict.<br />
<br />
<br />
=== Lazy Text ===<br />
<br />
TODO<br />
<br />
<br />
=== Strict Text ===<br />
<br />
TODO<br />
<br />
<br />
== Links ==<br />
<br />
* [[Performance/Strings]]<br />
<br />
* [[Wc]]<br />
<br />
* [https://groups.google.com/forum/?fromgroups#!topic/fa.haskell/QTP6cc6X6w4 Fast number parsing with strict bytestrings]<br />
<br />
* [http://hackage.haskell.org/package/string-conversions string-conversions]; this package provides a simple type class for converting values of different string types into values of other string types.<br />
<br />
* [http://hackage.haskell.org/package/convertible-text convertible-text], a text conversion package ([http://www.mail-archive.com/haskell-cafe@haskell.org/msg97795.html depricated])</div>Benmachinehttps://wiki.haskell.org/index.php?title=Pure&diff=56834Pure2013-09-15T01:36:05Z<p>Benmachine: Created page with "A function is called '''pure''' if it corresponds to a function in the mathematical sense: it associates each possible input value with an output value, and does nothing else...."</p>
<hr />
<div>A function is called '''pure''' if it corresponds to a function in the mathematical sense: it associates each possible input value with an output value, and does nothing else. In particular,<br />
<br />
* it has no ''side effects'', that is to say, invoking it produces no observable effect other than the result it returns; it cannot also ''e.g.'' write to disk, or print to a screen.<br />
* it does not depend on anything other than its parameters, so when invoked in a different context or at a different time with the same arguments, it will produce the same result.<br />
<br />
A programming language may be called '''purely functional''' if evaluation of expressions is pure.<br />
<br />
There has been some debate in the past as to the precise meaning of these terms. See also:<br />
<br />
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.7800 What is a Purely Functional Language?] a 1993 paper which presents a proposed formal definition of the concept,<br />
* [http://conal.net/blog/posts/the-c-language-is-purely-functional The C language is purely functional] (some satire intended),<br />
* [http://conal.net/blog/posts/is-haskell-a-purely-functional-language Is Haskell a purely functional language?]<br />
<br />
[[Category:Glossary]]</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine&diff=56833User:Benmachine2013-09-14T21:29:23Z<p>Benmachine: finished this</p>
<hr />
<div>I found a [[User:benmachine/hasktag_bug|bug with the &lt;hask&gt; tag]]. I put it on its own page so it doesn't ruin my user page.<br />
<br />
I wrote a [[User:benmachine/Cont|Cont tutorial]] of sorts.<br />
<br />
I have some objections to [[User:benmachine/Overqualified modules|module overqualification]]<br />
<br />
I wrote an [[User:benmachine/uninstall.sh|uninstall script]] for things cabal installs.</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine/Non-strict_semantics&diff=56832User:Benmachine/Non-strict semantics2013-09-14T21:29:05Z<p>Benmachine: Redirected page to Non-strict semantics</p>
<hr />
<div>#REDIRECT [[Non-strict semantics]]</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine/Non-strict_semantics&diff=56831User:Benmachine/Non-strict semantics2013-09-14T21:28:47Z<p>Benmachine: Moved rewrite to main location</p>
<hr />
<div>#REDIRECT Non-strict semantics</div>Benmachinehttps://wiki.haskell.org/index.php?title=Non-strict_semantics&diff=56830Non-strict semantics2013-09-14T21:28:33Z<p>Benmachine: Rewrote</p>
<hr />
<div>An expression language is said to have [[non-strict semantics]] if expressions can have a value even if some of their subexpressions do not. Haskell is one of the few modern languages to have non-strict semantics by default: nearly every other language has [[strict semantics]], in which if any subexpression fails to have a value, the whole expression fails with it.<br />
<br />
This is one of the most important features in Haskell: it is what allows programs to work with conceptually infinite data structures, and it is why people say that Haskell lets you write your own control structures. It's also one of the motivations behind Haskell being a [[Purity|pure]] language (though there are several other good ones).<br />
<br />
== What? ==<br />
<br />
Any sufficiently capable programming language is ''non-total'', which is to say you can write expressions that do not produce a value: common examples are an exception thrown, an infinite loop, or unproductive recursion, e.g. the following definition in Haskell:<br />
<br />
<haskell><br />
noreturn :: Integer -> Integer<br />
noreturn x = negate (noreturn x)<br />
</haskell><br />
<br />
or the following Python function:<br />
<br />
def noreturn(x):<br />
while True:<br />
x = -x<br />
<br />
return x # not reached<br />
<br />
both fail to produce a value when executed. We say that <tt>noreturn x</tt> is undefined, and write <tt>noreturn x = [[Bottom|⊥]]</tt>.<br />
<br />
In Python the following expression to check if <tt>2</tt> is in some list:<br />
<br />
2 in [2,4,noreturn(5)]<br />
<br />
also fails to have a value, because in order to construct the list, the interpreter tries to work out <tt>noreturn(5)</tt>, which of course doesn't return a value. This is called '''innermost-first''' evaluation: in order to call a function with some arguments, you first have to calculate what all the arguments are, starting from the innermost function call and working outwards. The result is that Python is ''strict'', in the sense that calling any function with an undefined argument produces an undefined value, i.e. <tt>f(⊥) = ⊥</tt>. If your language uses innermost-first evaluation, it correspondingly must have strict semantics.<br />
<br />
In Haskell, an analogous expression:<br />
<br />
<haskell><br />
elem 2 [2, 4, noreturn 5]<br />
</haskell><br />
<br />
in fact has the value <tt>True</tt>. The program does not have to compute <tt>noreturn 5</tt> because it is irrelevant to the overall value of the computation: only the values that are necessary to the result need be computed. This is called '''outermost-first''' evaluation because you first look at the outermost function call, <tt>elem</tt>, to see if it needs to use its arguments, and only if it does do you look at what those arguments are. This means that you can write a function that doesn't look at its argument, so it will return a value even if the argument is <tt>⊥</tt>. Such functions are ''not strict'', i.e. they satisfy <tt>f(⊥) ≠ ⊥</tt>. Practically, this means that Haskell functions need not completely compute their arguments before using them, which is why e.g. <tt>take 3 [1..]</tt> can produce <tt>[1,2,3]</tt> even though it is given a conceptually infinite list.<br />
<br />
Note that outermost-first evaluation is not the only way to have non-strict semantics: a speculative evaluation strategy, that evaluates arguments in parallel with the function in case they are needed later, could also be non-strict, as long as whenever the speculative evaluation failed, the evaluation of the function continued.<br />
<br />
Note also that in order for a function to be truly non-strict, it must return something without inspecting its argument ''at all''. You might think that doesn't sound like a very useful function, but remember that it might be e.g. a partial application: the function <tt>(||) True</tt>, or equivalently <tt>\x -> True || x</tt> does not need to inspect its argument, since <tt>True || x</tt> is always <tt>True</tt>. There are other examples, too: constructors like <tt>Just</tt> wrap their argument without inspecting it, and some other functions apply constructors before looking at the argument, and hence still produce a partial result, e.g. <tt>inits ⊥ = [] : ⊥</tt><br />
<br />
== Why? ==<br />
<br />
The important thing to understand about non-strict semantics is that it is not a performance feature. Non-strict semantics allows your language to only evaluate the things it needs to, but if you write your programs carefully, you'll only compute what is absolutely necessary ''anyway'', so the extra time your program spends working out what should and shouldn't be evaluated is time wasted. For this reason, a very well-optimised strict program will frequently outperform even the fastest non-strict program.<br />
<br />
However, the real and major advantage that non-strictness gives you over strict languages is you get to write cleaner and more composable code. In particular, you can separate ''production'' and ''consumption'' of data: don't know how many prime numbers you're going to need? Just make `primes` a list of ''all'' prime numbers, and then which ones actually get ''generated'' depends on how you use them in the rest of your code. By contrast, writing code in a strict language that constructs a data structure in response to demand usually will require first-class functions and/or a lot of manual hoop-jumping to make it all behave itself.<br />
<br />
Consider the following Haskell function definition:<br />
<br />
<haskell><br />
any :: (a -> Bool) -> [a] -> Bool<br />
any p = or . map p<br />
</haskell><br />
<br />
Here, <tt>map p</tt> replaces each element of the list with a boolean value representing whether or not that element satisfied <tt>p</tt>, then <tt>or</tt> checks if any of the booleans were <tt>True</tt>. Overall, then, <tt>any p xs</tt> tells you whether or not <tt>p x</tt> is <tt>True</tt> for any <tt>x</tt> in <tt>xs</tt>.<br />
<br />
Naively, it seems like this would be inefficient: first <tt>map</tt> processes the whole list, and then <tt>or</tt> finds any <tt>True</tt>s – but if the very first item of the list satisfies <tt>p</tt>, then you really didn't need to map over all the others.<br />
<br />
But in a non-strict context, even if both <tt>or</tt> and <tt>map</tt> are written completely naïvely, when <tt>or</tt> gets to the first <tt>True</tt> it stops asking for any more booleans, so <tt>map</tt> doesn't need to produce any more of them, and none of the rest of the list is visited.<br />
<br />
== But that's so weird! ==<br />
<br />
Not really! In non-strict languages you typically have evaluation driven by need, whereas in strict languages you have evaluation driven by function application. But functions are already for abstraction, so they end up serving a sort of dual purpose; meanwhile ordinary values can't really be used for abstraction, except if you know you're going to use their value at least once. If you don't, you have to wrap your value in a function that doesn't take any arguments, or in certain type systems where that doesn't make sense as a concept, you have to use a function that takes a single, boring argument, that it then ignores. You then have to duplicate the work if you want to use it twice, or else write some sort of caching, probably using mutable variables. On top of all that, you decide that function application isn't even the only method of driving evaluation, because you also need if-statements, loops, and other control structures that you have to bake right into the fabric of your language.<br />
<br />
In a strict langauge, to get the short-circuiting behaviour of <tt>any</tt> described in the previous section, you'd have little choice but to write out the whole recursion explicitly:<br />
<br />
<haskell><br />
any p [] = False<br />
any p (x:xs)<br />
| p x = True<br />
| otherwise = any p xs<br />
</haskell><br />
<br />
since in strict languages only builtin control structures can decide whether some bit of code gets executed or not, ordinary functions like <tt>or</tt> can't. You essentially duplicate the code of <tt>map</tt> iterating over the list and applying a function, and <tt>or</tt> folding the list with a binary operation.<br />
<br />
Meanwhile, in Haskell, functions are precisely for abstraction with parameters, and for abstraction without parameters, ordinary values suffice, whether you end up using them or not. All code, inside or outside functions, gets run when you need it and doesn't when you don't. You can easily write control structures as ordinary code:<br />
<br />
<haskell><br />
ifThenElse :: Bool -> a -> a -> a<br />
ifThenElse True x _ = x<br />
ifThenElse False _ y = y<br />
</haskell><br />
<br />
and this allows all sorts of interesting patterns to be abstracted in an incredibly lightweight fashion. Labelled for-loops are a ''library'' in Haskell, rather than requiring special syntax and language support.<br />
<br />
== How do I stop it? ==<br />
<br />
As mentioned above, non-strictness can hurt performance, e.g. if a result is definitely going to be needed later, you might as well evaluate it now, to avoid having to hold on to all the data that goes into it. Fortunately, the Haskell designers were aware of these problems and introduced a loophole or two so that we could force our programs to be strict when necessary: see [[Performance/Strictness]] and [[seq]].<br />
<br />
[[Category:Glossary]]</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine/Non-strict_semantics&diff=56829User:Benmachine/Non-strict semantics2013-09-14T20:25:22Z<p>Benmachine: </p>
<hr />
<div>An expression language is said to have [[non-strict semantics]] if expressions can have a value even if some of their subexpressions do not. Haskell is one of the few modern languages to have non-strict semantics by default: nearly every other language has [[strict semantics]], in which if any subexpression fails to have a value, the whole expression fails with it.<br />
<br />
This is one of the most important features in Haskell: it is what allows programs to work with conceptually infinite data structures, and it is why people say that Haskell lets you write your own control structures. It's also one of the motivations behind Haskell being a [[Purity|pure]] language (though there are several other good ones).<br />
<br />
== What? ==<br />
<br />
Any sufficiently capable programming language is ''non-total'', which is to say you can write expressions that do not produce a value: common examples are an exception thrown, an infinite loop, or unproductive recursion, e.g. the following definition in Haskell:<br />
<br />
<haskell><br />
noreturn :: Integer -> Integer<br />
noreturn x = negate (noreturn x)<br />
</haskell><br />
<br />
or the following Python function:<br />
<br />
def noreturn(x):<br />
while True:<br />
x = -x<br />
<br />
return x # not reached<br />
<br />
both fail to produce a value when executed. We say that <tt>noreturn x</tt> is undefined, and write <tt>noreturn x = [[Bottom|⊥]]</tt>.<br />
<br />
In Python the following expression to check if <tt>2</tt> is in some list:<br />
<br />
2 in [2,4,noreturn(5)]<br />
<br />
also fails to have a value, because in order to construct the list, the interpreter tries to work out <tt>noreturn(5)</tt>, which of course doesn't return a value. This is called '''innermost-first''' evaluation: in order to call a function with some arguments, you first have to calculate what all the arguments are, starting from the innermost function call and working outwards. The result is that Python is ''strict'', in the sense that calling any function with an undefined argument produces an undefined value, i.e. <tt>f(⊥) = ⊥</tt>. If your language uses innermost-first evaluation, it correspondingly must have strict semantics.<br />
<br />
In Haskell, an analogous expression:<br />
<br />
<haskell><br />
elem 2 [2, 4, noreturn 5]<br />
</haskell><br />
<br />
in fact has the value <tt>True</tt>. The program does not have to compute <tt>noreturn 5</tt> because it is irrelevant to the overall value of the computation: only the values that are necessary to the result need be computed. This is called '''outermost-first''' evaluation because you first look at the outermost function call, <tt>elem</tt>, to see if it needs to use its arguments, and only if it does do you look at what those arguments are. This means that you can write a function that doesn't look at its argument, so it will return a value even if the argument is <tt>⊥</tt>. Such functions are ''not strict'', i.e. they satisfy <tt>f(⊥) ≠ ⊥</tt>. Practically, this means that Haskell functions need not completely compute their arguments before using them, which is why e.g. <tt>take 3 [1..]</tt> can produce <tt>[1,2,3]</tt> even though it is given a conceptually infinite list.<br />
<br />
Note that outermost-first evaluation is not the only way to have non-strict semantics: a speculative evaluation strategy, that evaluates arguments in parallel with the function in case they are needed later, could also be non-strict, as long as whenever the speculative evaluation failed, the evaluation of the function continued.<br />
<br />
Note also that in order for a function to be truly non-strict, it must return something without inspecting its argument ''at all''. You might think that doesn't sound like a very useful function, but remember that it might be e.g. a partial application: the function <tt>(||) True</tt>, or equivalently <tt>\x -> True || x</tt> does not need to inspect its argument, since <tt>True || x</tt> is always <tt>True</tt>. There are other examples, too: constructors like <tt>Just</tt> wrap their argument without inspecting it, and some other functions apply constructors before looking at the argument, and hence still produce a partial result, e.g. <tt>inits ⊥ = [] : ⊥</tt><br />
<br />
== Why? ==<br />
<br />
The important thing to understand about non-strict semantics is that it is not a performance feature. Non-strict semantics allows your language to only evaluate the things it needs to, but if you write your programs carefully, you'll only compute what is absolutely necessary ''anyway'', so the extra time your program spends working out what should and shouldn't be evaluated is time wasted. For this reason, a very well-optimised strict program will frequently outperform even the fastest non-strict program.<br />
<br />
However, the real and major advantage that non-strictness gives you over strict languages is you get to write cleaner and more composable code. In particular, you can separate ''production'' and ''consumption'' of data: don't know how many prime numbers you're going to need? Just make `primes` a list of ''all'' prime numbers, and then which ones actually get ''generated'' depends on how you use them in the rest of your code. By contrast, writing code in a strict language that constructs a data structure in response to demand usually will require first-class functions and/or a lot of manual hoop-jumping to make it all behave itself.<br />
<br />
Consider the following Haskell function definition:<br />
<br />
<haskell><br />
any :: (a -> Bool) -> [a] -> Bool<br />
any p = or . map p<br />
</haskell><br />
<br />
Here, <tt>map p</tt> replaces each element of the list with a boolean value representing whether or not that element satisfied <tt>p</tt>, then <tt>or</tt> checks if any of the booleans were <tt>True</tt>. Overall, then, <tt>any p xs</tt> tells you whether or not <tt>p x</tt> is <tt>True</tt> for any <tt>x</tt> in <tt>xs</tt>.<br />
<br />
Naively, it seems like this would be inefficient: first <tt>map</tt> processes the whole list, and then <tt>or</tt> finds any <tt>True</tt>s – but if the very first item of the list satisfies <tt>p</tt>, then you really didn't need to map over all the others.<br />
<br />
But in a non-strict context, even if both <tt>or</tt> and <tt>map</tt> are written completely naïvely, when <tt>or</tt> gets to the first <tt>True</tt> it stops asking for any more booleans, so <tt>map</tt> doesn't need to produce any more of them, and none of the rest of the list is visited.<br />
<br />
== But that's so weird! ==<br />
<br />
Not really! In non-strict languages you typically have evaluation driven by need, whereas in strict languages you have evaluation driven by function application. But functions are already for abstraction, so they end up serving a sort of dual purpose; meanwhile ordinary values can't really be used for abstraction, except if you know you're going to use their value at least once. If you don't, you have to wrap your value in a function that doesn't take any arguments, or in certain type systems where that doesn't make sense as a concept, you have to use a function that takes a single, boring argument, that it then ignores. You then have to duplicate the work if you want to use it twice, or else write some sort of caching, probably using mutable variables. On top of all that, you decide that function application isn't even the only method of driving evaluation, because you also need if-statements, loops, and other control structures that you have to bake right into the fabric of your language.<br />
<br />
In a strict langauge, to get the short-circuiting behaviour of <tt>any</tt> described in the previous section, you'd have little choice but to write out the whole recursion explicitly:<br />
<br />
<haskell><br />
any p [] = False<br />
any p (x:xs)<br />
| p x = True<br />
| otherwise = any p xs<br />
</haskell><br />
<br />
since in strict languages only builtin control structures can decide whether some bit of code gets executed or not, ordinary functions like <tt>or</tt> can't. You essentially duplicate the code of <tt>map</tt> iterating over the list and applying a function, and <tt>or</tt> folding the list with a binary operation.<br />
<br />
Meanwhile, in Haskell, functions are precisely for abstraction with parameters, and for abstraction without parameters, ordinary values suffice, whether you end up using them or not. All code, inside or outside functions, gets run when you need it and doesn't when you don't. You can easily write control structures as ordinary code:<br />
<br />
<haskell><br />
ifThenElse :: Bool -> a -> a -> a<br />
ifThenElse True x _ = x<br />
ifThenElse False _ y = y<br />
</haskell><br />
<br />
and this allows all sorts of interesting patterns to be abstracted in an incredibly lightweight fashion. Labelled for-loops are a ''library'' in Haskell, rather than requiring special syntax and language support.<br />
<br />
== How do I stop it? ==<br />
<br />
As mentioned above, non-strictness can hurt performance, e.g. if a result is definitely going to be needed later, you might as well evaluate it now, to avoid having to hold on to all the data that goes into it. Fortunately, the Haskell designers were aware of these problems and introduced a loophole or two so that we could force our programs to be strict when necessary: see [[Performance/Strictness]] and [[seq]].</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine/Non-strict_semantics&diff=56828User:Benmachine/Non-strict semantics2013-09-14T20:07:27Z<p>Benmachine: Why non-strictness matters</p>
<hr />
<div>An expression language is said to have [[non-strict semantics]] if expressions can have a value even if some of their subexpressions do not. Haskell is one of the few modern languages to have non-strict semantics by default: nearly every other language has [[strict semantics]], in which if any subexpression fails to have a value, the whole expression fails with it.<br />
<br />
This is one of the most important features in Haskell: it is what allows programs to work with conceptually infinite data structures, and it is why people say that Haskell lets you write your own control structures. It's also one of the motivations behind Haskell being a [[Purity|pure]] language (though there are several other good ones).<br />
<br />
== What? ==<br />
<br />
Any sufficiently capable programming language is ''non-total'', which is to say you can write expressions that do not produce a value: common examples are an exception thrown, an infinite loop, or unproductive recursion, e.g. the following definition in Haskell:<br />
<br />
<haskell><br />
noreturn :: Integer -> Integer<br />
noreturn x = negate (noreturn x)<br />
</haskell><br />
<br />
or the following Python function:<br />
<br />
def noreturn(x):<br />
while True:<br />
x = -x<br />
<br />
return x # not reached<br />
<br />
both fail to produce a value when executed. We say that <tt>noreturn x</tt> is undefined, and write <tt>noreturn x = [[Bottom|⊥]]</tt>.<br />
<br />
In Python the following expression to check if <tt>2</tt> is in some list:<br />
<br />
2 in [2,4,noreturn(5)]<br />
<br />
also fails to have a value, because in order to construct the list, the interpreter tries to work out <tt>noreturn(5)</tt>, which of course doesn't return a value. This is called '''innermost-first''' evaluation: in order to call a function with some arguments, you first have to calculate what all the arguments are, starting from the innermost function call and working outwards. The result is that Python is ''strict'', in the sense that calling any function with an undefined argument produces an undefined value, i.e. <tt>f(⊥) = ⊥</tt>. If your language uses innermost-first evaluation, it correspondingly must have strict semantics.<br />
<br />
In Haskell, an analogous expression:<br />
<br />
<haskell><br />
elem 2 [2, 4, noreturn 5]<br />
</haskell><br />
<br />
in fact has the value <tt>True</tt>. The program does not have to compute <tt>noreturn 5</tt> because it is irrelevant to the overall value of the computation: only the values that are necessary to the result need be computed. This is called '''outermost-first''' evaluation because you first look at the outermost function call, <tt>elem</tt>, to see if it needs to use its arguments, and only if it does do you look at what those arguments are. This means that you can write a function that doesn't look at its argument, so it will return a value even if the argument is <tt>⊥</tt>. Such functions are ''not strict'', i.e. they satisfy <tt>f(⊥) ≠ ⊥</tt>. Practically, this means that Haskell functions need not completely compute their arguments before using them, which is why e.g. <tt>take 3 [1..]</tt> can produce <tt>[1,2,3]</tt> even though it is given a conceptually infinite list.<br />
<br />
Note that outermost-first evaluation is not the only way to have non-strict semantics: a speculative evaluation strategy, that evaluates arguments in parallel with the function in case they are needed later, could also be non-strict, as long as whenever the speculative evaluation failed, the evaluation of the function continued.<br />
<br />
Note also that in order for a function to be truly non-strict, it must return something without inspecting its argument ''at all''. You might think that doesn't sound like a very useful function, but remember that it might be e.g. a partial application: the function <tt>(||) True</tt>, or equivalently <tt>\x -> True || x</tt> does not need to inspect its argument, since <tt>True || x</tt> is always <tt>True</tt>. There are other examples, too: constructors like <tt>Just</tt> wrap their argument without inspecting it, and some other functions apply constructors before looking at the argument, and hence still produce a partial result, e.g. <tt>inits ⊥ = [] : ⊥</tt><br />
<br />
== Why? ==<br />
<br />
The important thing to understand about non-strict semantics is that it is not a performance feature. Non-strict semantics allows your language to only evaluate the things it needs to, but if you write your programs carefully, you'll only compute what is absolutely necessary ''anyway'', so the extra time your program spends working out what should and shouldn't be evaluated is time wasted. For this reason, a very well-optimised strict program will frequently outperform even the fastest non-strict program.<br />
<br />
However, the real and major advantage that non-strictness gives you over strict languages is you get to write cleaner and more composable code. In particular, you can separate ''production'' and ''consumption'' of data: don't know how many prime numbers you're going to need? Just make `primes` a list of ''all'' prime numbers, and then which ones actually get ''generated'' depends on how you use them in the rest of your code. By contrast, writing code in a strict language that constructs a data structure in response to demand usually will require first-class functions and/or a lot of manual hoop-jumping to make it all behave itself.<br />
<br />
Consider the following Haskell function definition:<br />
<br />
<haskell><br />
any :: (a -> Bool) -> [a] -> Bool<br />
any p = or . map p<br />
</haskell><br />
<br />
Because <tt>or</tt> uses non-strictness to stop at the first <tt>True</tt> in the input, <tt>map</tt> doesn't even need to know that only the first half of the list might be needed. We can write <tt>map</tt> in the completely straightforward and obviously correct way, and still have it interact well with <tt>or</tt> in this way; <tt>map</tt> produces data, <tt>or</tt> consumes it, and the two are properly decoupled.<br />
<br />
In a strict langauge, you'd have to write the recursion out manually:<br />
<br />
<haskell><br />
any p [] = False<br />
any p (x:xs)<br />
| p x = True<br />
| otherwise = any p xs<br />
</haskell><br />
<br />
since in strict languages only builtin control structures can decide whether some bit of code gets executed or not, ordinary functions like <tt>or</tt> can't.<br />
<br />
It's this additional power that Haskell has that leads people to say you can define your own control structures as normal Haskell functions, which allows all sorts of interesting patterns to be abstracted in an incredibly lightweight fashion. Labelled for-loops are a ''library'' in Haskell, rather than requiring special syntax and language support.<br />
<br />
== How do I stop it? ==<br />
<br />
As mentioned above, non-strictness can hurt performance, e.g. if a result is definitely going to be needed later, you might as well evaluate it now, to avoid having to hold on to all the data that goes into it. Fortunately, the Haskell designers were aware of these problems and introduced a loophole or two so that we could force our programs to be strict when necessary: see [[Performance/Strictness]] and [[seq]].</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine/Non-strict_semantics&diff=56827User:Benmachine/Non-strict semantics2013-09-14T20:06:51Z<p>Benmachine: Upgrade all the headings from h3s to h2s</p>
<hr />
<div>An expression language is said to have [[non-strict semantics]] if expressions can have a value even if some of their subexpressions do not. Haskell is one of the few modern languages to have non-strict semantics by default: nearly every other language has [[strict semantics]], in which if any subexpression fails to have a value, the whole expression fails with it.<br />
<br />
== What? ==<br />
<br />
Any sufficiently capable programming language is ''non-total'', which is to say you can write expressions that do not produce a value: common examples are an exception thrown, an infinite loop, or unproductive recursion, e.g. the following definition in Haskell:<br />
<br />
<haskell><br />
noreturn :: Integer -> Integer<br />
noreturn x = negate (noreturn x)<br />
</haskell><br />
<br />
or the following Python function:<br />
<br />
def noreturn(x):<br />
while True:<br />
x = -x<br />
<br />
return x # not reached<br />
<br />
both fail to produce a value when executed. We say that <tt>noreturn x</tt> is undefined, and write <tt>noreturn x = [[Bottom|⊥]]</tt>.<br />
<br />
In Python the following expression to check if <tt>2</tt> is in some list:<br />
<br />
2 in [2,4,noreturn(5)]<br />
<br />
also fails to have a value, because in order to construct the list, the interpreter tries to work out <tt>noreturn(5)</tt>, which of course doesn't return a value. This is called '''innermost-first''' evaluation: in order to call a function with some arguments, you first have to calculate what all the arguments are, starting from the innermost function call and working outwards. The result is that Python is ''strict'', in the sense that calling any function with an undefined argument produces an undefined value, i.e. <tt>f(⊥) = ⊥</tt>. If your language uses innermost-first evaluation, it correspondingly must have strict semantics.<br />
<br />
In Haskell, an analogous expression:<br />
<br />
<haskell><br />
elem 2 [2, 4, noreturn 5]<br />
</haskell><br />
<br />
in fact has the value <tt>True</tt>. The program does not have to compute <tt>noreturn 5</tt> because it is irrelevant to the overall value of the computation: only the values that are necessary to the result need be computed. This is called '''outermost-first''' evaluation because you first look at the outermost function call, <tt>elem</tt>, to see if it needs to use its arguments, and only if it does do you look at what those arguments are. This means that you can write a function that doesn't look at its argument, so it will return a value even if the argument is <tt>⊥</tt>. Such functions are ''not strict'', i.e. they satisfy <tt>f(⊥) ≠ ⊥</tt>. Practically, this means that Haskell functions need not completely compute their arguments before using them, which is why e.g. <tt>take 3 [1..]</tt> can produce <tt>[1,2,3]</tt> even though it is given a conceptually infinite list.<br />
<br />
Note that outermost-first evaluation is not the only way to have non-strict semantics: a speculative evaluation strategy, that evaluates arguments in parallel with the function in case they are needed later, could also be non-strict, as long as whenever the speculative evaluation failed, the evaluation of the function continued.<br />
<br />
Note also that in order for a function to be truly non-strict, it must return something without inspecting its argument ''at all''. You might think that doesn't sound like a very useful function, but remember that it might be e.g. a partial application: the function <tt>(||) True</tt>, or equivalently <tt>\x -> True || x</tt> does not need to inspect its argument, since <tt>True || x</tt> is always <tt>True</tt>. There are other examples, too: constructors like <tt>Just</tt> wrap their argument without inspecting it, and some other functions apply constructors before looking at the argument, and hence still produce a partial result, e.g. <tt>inits ⊥ = [] : ⊥</tt><br />
<br />
== Why? ==<br />
<br />
The important thing to understand about non-strict semantics is that it is not a performance feature. Non-strict semantics allows your language to only evaluate the things it needs to, but if you write your programs carefully, you'll only compute what is absolutely necessary ''anyway'', so the extra time your program spends working out what should and shouldn't be evaluated is time wasted. For this reason, a very well-optimised strict program will frequently outperform even the fastest non-strict program.<br />
<br />
However, the real and major advantage that non-strictness gives you over strict languages is you get to write cleaner and more composable code. In particular, you can separate ''production'' and ''consumption'' of data: don't know how many prime numbers you're going to need? Just make `primes` a list of ''all'' prime numbers, and then which ones actually get ''generated'' depends on how you use them in the rest of your code. By contrast, writing code in a strict language that constructs a data structure in response to demand usually will require first-class functions and/or a lot of manual hoop-jumping to make it all behave itself.<br />
<br />
Consider the following Haskell function definition:<br />
<br />
<haskell><br />
any :: (a -> Bool) -> [a] -> Bool<br />
any p = or . map p<br />
</haskell><br />
<br />
Because <tt>or</tt> uses non-strictness to stop at the first <tt>True</tt> in the input, <tt>map</tt> doesn't even need to know that only the first half of the list might be needed. We can write <tt>map</tt> in the completely straightforward and obviously correct way, and still have it interact well with <tt>or</tt> in this way; <tt>map</tt> produces data, <tt>or</tt> consumes it, and the two are properly decoupled.<br />
<br />
In a strict langauge, you'd have to write the recursion out manually:<br />
<br />
<haskell><br />
any p [] = False<br />
any p (x:xs)<br />
| p x = True<br />
| otherwise = any p xs<br />
</haskell><br />
<br />
since in strict languages only builtin control structures can decide whether some bit of code gets executed or not, ordinary functions like <tt>or</tt> can't.<br />
<br />
It's this additional power that Haskell has that leads people to say you can define your own control structures as normal Haskell functions, which allows all sorts of interesting patterns to be abstracted in an incredibly lightweight fashion. Labelled for-loops are a ''library'' in Haskell, rather than requiring special syntax and language support.<br />
<br />
== How do I stop it? ==<br />
<br />
As mentioned above, non-strictness can hurt performance, e.g. if a result is definitely going to be needed later, you might as well evaluate it now, to avoid having to hold on to all the data that goes into it. Fortunately, the Haskell designers were aware of these problems and introduced a loophole or two so that we could force our programs to be strict when necessary: see [[Performance/Strictness]] and [[seq]].</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine/Non-strict_semantics&diff=56825User:Benmachine/Non-strict semantics2013-09-14T18:02:33Z<p>Benmachine: /* What? */</p>
<hr />
<div>An expression language is said to have [[non-strict semantics]] if expressions can have a value even if some of their subexpressions do not. Haskell is one of the few modern languages to have non-strict semantics by default: nearly every other language has [[strict semantics]], in which if any subexpression fails to have a value, the whole expression fails with it.<br />
<br />
=== What? ===<br />
<br />
Any sufficiently capable programming language is ''non-total'', which is to say you can write expressions that do not produce a value: common examples are an exception thrown, an infinite loop, or unproductive recursion, e.g. the following definition in Haskell:<br />
<br />
<haskell><br />
noreturn :: Integer -> Integer<br />
noreturn x = negate (noreturn x)<br />
</haskell><br />
<br />
or the following Python function:<br />
<br />
def noreturn(x):<br />
while True:<br />
x = -x<br />
<br />
return x # not reached<br />
<br />
both fail to produce a value when executed. We say that <tt>noreturn x</tt> is undefined, and write <tt>noreturn x = [[Bottom|⊥]]</tt>.<br />
<br />
In Python the following expression to check if <tt>2</tt> is in some list:<br />
<br />
2 in [2,4,noreturn(5)]<br />
<br />
also fails to have a value, because in order to construct the list, the interpreter tries to work out <tt>noreturn(5)</tt>, which of course doesn't return a value. This is called '''innermost-first''' evaluation: in order to call a function with some arguments, you first have to calculate what all the arguments are, starting from the innermost function call and working outwards. The result is that Python is ''strict'', in the sense that calling any function with an undefined argument produces an undefined value, i.e. <tt>f(⊥) = ⊥</tt>. If your language uses innermost-first evaluation, it correspondingly must have strict semantics.<br />
<br />
In Haskell, an analogous expression:<br />
<br />
<haskell><br />
elem 2 [2, 4, noreturn 5]<br />
</haskell><br />
<br />
in fact has the value <tt>True</tt>. The program does not have to compute <tt>noreturn 5</tt> because it is irrelevant to the overall value of the computation: only the values that are necessary to the result need be computed. This is called '''outermost-first''' evaluation because you first look at the outermost function call, <tt>elem</tt>, to see if it needs to use its arguments, and only if it does do you look at what those arguments are. This means that you can write a function that doesn't look at its argument, so it will return a value even if the argument is <tt>⊥</tt>. Such functions are ''not strict'', i.e. they satisfy <tt>f(⊥) ≠ ⊥</tt>. Practically, this means that Haskell functions need not completely compute their arguments before using them, which is why e.g. <tt>take 3 [1..]</tt> can produce <tt>[1,2,3]</tt> even though it is given a conceptually infinite list.<br />
<br />
Note that outermost-first evaluation is not the only way to have non-strict semantics: a speculative evaluation strategy, that evaluates arguments in parallel with the function in case they are needed later, could also be non-strict, as long as whenever the speculative evaluation failed, the evaluation of the function continued.<br />
<br />
Note also that in order for a function to be truly non-strict, it must return something without inspecting its argument ''at all''. You might think that doesn't sound like a very useful function, but remember that it might be e.g. a partial application: the function <tt>(||) True</tt>, or equivalently <tt>\x -> True || x</tt> does not need to inspect its argument, since <tt>True || x</tt> is always <tt>True</tt>. There are other examples, too: constructors like <tt>Just</tt> wrap their argument without inspecting it, and some other functions apply constructors before looking at the argument, and hence still produce a partial result, e.g. <tt>inits ⊥ = [] : ⊥</tt><br />
<br />
=== Why? ===<br />
<br />
The important thing to understand about non-strict semantics is that it is not a performance feature. Non-strict semantics allows your language to only evaluate the things it needs to, but if you write your programs carefully, you'll only compute what is absolutely necessary ''anyway'', so the extra time your program spends working out what should and shouldn't be evaluated is time wasted. For this reason, a very well-optimised strict program will frequently outperform even the fastest non-strict program.<br />
<br />
However, the real and major advantage that non-strictness gives you over strict languages is you get to write cleaner and more composable code. In particular, you can separate ''production'' and ''consumption'' of data: don't know how many prime numbers you're going to need? Just make `primes` a list of ''all'' prime numbers, and then which ones actually get ''generated'' depends on how you use them in the rest of your code. By contrast, writing code in a strict language that constructs a data structure in response to demand usually will require first-class functions and/or a lot of manual hoop-jumping to make it all behave itself.<br />
<br />
Consider the following Haskell function definition:<br />
<br />
<haskell><br />
any :: (a -> Bool) -> [a] -> Bool<br />
any p = or . map p<br />
</haskell><br />
<br />
Because <tt>or</tt> uses non-strictness to stop at the first <tt>True</tt> in the input, <tt>map</tt> doesn't even need to know that only the first half of the list might be needed. We can write <tt>map</tt> in the completely straightforward and obviously correct way, and still have it interact well with <tt>or</tt> in this way; <tt>map</tt> produces data, <tt>or</tt> consumes it, and the two are properly decoupled.<br />
<br />
In a strict langauge, you'd have to write the recursion out manually:<br />
<br />
<haskell><br />
any p [] = False<br />
any p (x:xs)<br />
| p x = True<br />
| otherwise = any p xs<br />
</haskell><br />
<br />
since in strict languages only builtin control structures can decide whether some bit of code gets executed or not, ordinary functions like <tt>or</tt> can't.<br />
<br />
It's this additional power that Haskell has that leads people to say you can define your own control structures as normal Haskell functions, which allows all sorts of interesting patterns to be abstracted in an incredibly lightweight fashion. Labelled for-loops are a ''library'' in Haskell, rather than requiring special syntax and language support.<br />
<br />
=== How do I stop it? ===<br />
<br />
As mentioned above, non-strictness can hurt performance, e.g. if a result is definitely going to be needed later, you might as well evaluate it now, to avoid having to hold on to all the data that goes into it. Fortunately, the Haskell designers were aware of these problems and introduced a loophole or two so that we could force our programs to be strict when necessary: see [[Performance/Strictness]] and [[seq]].</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine/Non-strict_semantics&diff=56824User:Benmachine/Non-strict semantics2013-09-14T18:01:29Z<p>Benmachine: /* What? */</p>
<hr />
<div>An expression language is said to have [[non-strict semantics]] if expressions can have a value even if some of their subexpressions do not. Haskell is one of the few modern languages to have non-strict semantics by default: nearly every other language has [[strict semantics]], in which if any subexpression fails to have a value, the whole expression fails with it.<br />
<br />
=== What? ===<br />
<br />
Any sufficiently capable programming language is ''non-total'', which is to say you can write expressions that do not produce a value: common examples are an exception thrown, an infinite loop, or unproductive recursion, e.g. the following definition in Haskell:<br />
<br />
<haskell><br />
noreturn :: Integer -> Integer<br />
noreturn x = negate (noreturn x)<br />
</haskell><br />
<br />
or the following Python function:<br />
<br />
def noreturn(x):<br />
while True:<br />
x = -x<br />
<br />
return x # not reached<br />
<br />
both fail to produce a value when executed. We say that <tt>noreturn x</tt> is undefined, and write <tt>noreturn x = [[Bottom|⊥]]</tt>.<br />
<br />
In Python the following expression to check if <tt>2</tt> is in some list:<br />
<br />
2 in [2,4,noreturn(5)]<br />
<br />
also fails to have a value, because in order to construct the list, the interpreter tries to work out <tt>noreturn(5)</tt>, which of course doesn't return a value. This is called '''innermost-first''' evaluation: in order to call a function with some arguments, you first have to calculate what all the arguments are, starting from the innermost function call and working outwards. The result is that Python is ''strict'', in the sense that calling any function with an undefined argument produces an undefined value, i.e. <tt>f(⊥) = ⊥</tt>. If your language uses innermost-first evaluation, it correspondingly must have strict semantics.<br />
<br />
In Haskell, an analogous expression:<br />
<br />
<haskell><br />
elem 2 [2, 4, noreturn 5]<br />
</haskell><br />
<br />
in fact has the value <tt>True</tt>. The program does not have to compute <tt>noreturn 5</tt> because it is irrelevant to the overall value of the computation: only the values that are necessary to the result need be computed. This is called '''outermost-first''' evaluation because you first look at the outermost function call, <tt>elem</tt>, to see if it needs to use its arguments, and only if it does do you look at what those arguments are. This means that you can write a function that doesn't look at its argument, so it will return a value even if the argument is <tt>⊥</tt>. Such functions are ''not strict'', i.e. they satisfy <tt>f(⊥) ≠ ⊥</tt>. Practically, this means that Haskell functions need not completely compute their arguments before using them, which is why e.g. <tt>take 3 [1..]</tt> can produce <tt>[1,2,3]</tt> even though it is given a conceptually infinite list.<br />
<br />
Note that outermost-first evaluation is not the only way to have non-strict semantics: a speculative evaluation strategy, that evaluates arguments in parallel with the function in case they are needed later, could also be non-strict, as long as whenever the speculative evaluation failed, the evaluation of the function continued.<br />
<br />
Note also that in order for a function to be truly non-strict, it must return something without inspecting its argument ''at all''. You might think that doesn't sound like a very useful function, but remember that it might be e.g. a partial application: the function <tt>(||) True</tt>, or equivalently <tt>\x -> True || x</tt> does not need to inspect its argument, since <tt>True || x</tt> is always <tt>True</tt>. There are other examples, too: constructors like <tt>Just</tt> wrap their argument without inspecting it, and some other functions apply constructors ''before'' looking at the argument, and hence still produce a partial result, e.g. <tt>inits ⊥ = [] : ⊥</tt><br />
<br />
=== Why? ===<br />
<br />
The important thing to understand about non-strict semantics is that it is not a performance feature. Non-strict semantics allows your language to only evaluate the things it needs to, but if you write your programs carefully, you'll only compute what is absolutely necessary ''anyway'', so the extra time your program spends working out what should and shouldn't be evaluated is time wasted. For this reason, a very well-optimised strict program will frequently outperform even the fastest non-strict program.<br />
<br />
However, the real and major advantage that non-strictness gives you over strict languages is you get to write cleaner and more composable code. In particular, you can separate ''production'' and ''consumption'' of data: don't know how many prime numbers you're going to need? Just make `primes` a list of ''all'' prime numbers, and then which ones actually get ''generated'' depends on how you use them in the rest of your code. By contrast, writing code in a strict language that constructs a data structure in response to demand usually will require first-class functions and/or a lot of manual hoop-jumping to make it all behave itself.<br />
<br />
Consider the following Haskell function definition:<br />
<br />
<haskell><br />
any :: (a -> Bool) -> [a] -> Bool<br />
any p = or . map p<br />
</haskell><br />
<br />
Because <tt>or</tt> uses non-strictness to stop at the first <tt>True</tt> in the input, <tt>map</tt> doesn't even need to know that only the first half of the list might be needed. We can write <tt>map</tt> in the completely straightforward and obviously correct way, and still have it interact well with <tt>or</tt> in this way; <tt>map</tt> produces data, <tt>or</tt> consumes it, and the two are properly decoupled.<br />
<br />
In a strict langauge, you'd have to write the recursion out manually:<br />
<br />
<haskell><br />
any p [] = False<br />
any p (x:xs)<br />
| p x = True<br />
| otherwise = any p xs<br />
</haskell><br />
<br />
since in strict languages only builtin control structures can decide whether some bit of code gets executed or not, ordinary functions like <tt>or</tt> can't.<br />
<br />
It's this additional power that Haskell has that leads people to say you can define your own control structures as normal Haskell functions, which allows all sorts of interesting patterns to be abstracted in an incredibly lightweight fashion. Labelled for-loops are a ''library'' in Haskell, rather than requiring special syntax and language support.<br />
<br />
=== How do I stop it? ===<br />
<br />
As mentioned above, non-strictness can hurt performance, e.g. if a result is definitely going to be needed later, you might as well evaluate it now, to avoid having to hold on to all the data that goes into it. Fortunately, the Haskell designers were aware of these problems and introduced a loophole or two so that we could force our programs to be strict when necessary: see [[Performance/Strictness]] and [[seq]].</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine/Non-strict_semantics&diff=56823User:Benmachine/Non-strict semantics2013-09-14T17:53:33Z<p>Benmachine: </p>
<hr />
<div>An expression language is said to have [[non-strict semantics]] if expressions can have a value even if some of their subexpressions do not. Haskell is one of the few modern languages to have non-strict semantics by default: nearly every other language has [[strict semantics]], in which if any subexpression fails to have a value, the whole expression fails with it.<br />
<br />
=== What? ===<br />
<br />
Any sufficiently capable programming language is ''non-total'', which is to say you can write expressions that do not produce a value: common examples are an exception thrown, an infinite loop, or unproductive recursion, e.g. the following definition in Haskell:<br />
<br />
<haskell><br />
noreturn :: Integer -> Integer<br />
noreturn x = negate (noreturn x)<br />
</haskell><br />
<br />
or the following Python function:<br />
<br />
def noreturn(x):<br />
while True:<br />
x = -x<br />
<br />
return x # not reached<br />
<br />
both fail to produce a value when executed. We say that <tt>noreturn x</tt> is undefined, and write <tt>noreturn x = [[Bottom|⊥]]</tt>.<br />
<br />
In Python the following expression to check if <tt>2</tt> is in some list:<br />
<br />
2 in [2,4,noreturn(5)]<br />
<br />
also fails to have a value, because in order to construct the list, the interpreter tries to work out <tt>noreturn(5)</tt>, which of course doesn't return a value. This is called '''innermost-first''' evaluation: in order to call a function with some arguments, you first have to calculate what all the arguments are, starting from the innermost function call and working outwards. The result is that Python is strict, in the sense that calling any function with an undefined argument produces an undefined value, i.e. <tt>f(⊥) = ⊥</tt>. If your language uses innermost-first evaluation, it correspondingly must have strict semantics.<br />
<br />
In Haskell, an analogous expression:<br />
<br />
<haskell><br />
elem 2 [2, 4, noreturn 5]<br />
</haskell><br />
<br />
in fact has the value <tt>True</tt>. The program does not have to compute <tt>noreturn 5</tt> because it is irrelevant to the overall value of the computation: only the values that are necessary to the result need be computed. This is called '''outermost-first''' evaluation because you first look at the outermost function call, <tt>elem</tt>, to see if it needs to use its arguments, and only if it does do you look at what those arguments are. This means that you can write a function that doesn't look at its argument, so it will return a value even if the argument is <tt>⊥</tt>. Such functions are not strict, i.e. they satisfy <tt>f(⊥) ≠ ⊥</tt>. Practically, this means that Haskell functions need not completely compute their arguments before using them, which is why e.g. <tt>take 3 [1..]</tt> can produce <tt>[1,2,3]</tt> even though it is given a conceptually infinite list.<br />
<br />
Note that outermost-first evaluation is not the only way to have non-strict semantics: a speculative evaluation strategy, that evaluated arguments in parallel with the function in case they were needed later, could also be non-strict, as long as whenever the speculative evaluation failed, the evaluation of the function continued.<br />
<br />
Note also that in order for a function to be truly non-strict, it must return something without inspecting its argument ''at all''. You might think that doesn't sound like a very useful function, but remember that it might be e.g. a partial application: the function <tt>(||) True</tt>, or equivalently <tt>\x -> True || x</tt> does not need to inspect its argument, since <tt>True || x</tt> is always <tt>True</tt>. There are other examples, too: constructors like <tt>Just</tt> wrap their argument without inspecting it, and some other functions apply constructors ''before'' looking at the argument, and hence still produce a partial result, e.g. <tt>inits ⊥ = [] : ⊥</tt><br />
<br />
=== Why? ===<br />
<br />
The important thing to understand about non-strict semantics is that it is not a performance feature. Non-strict semantics allows your language to only evaluate the things it needs to, but if you write your programs carefully, you'll only compute what is absolutely necessary ''anyway'', so the extra time your program spends working out what should and shouldn't be evaluated is time wasted. For this reason, a very well-optimised strict program will frequently outperform even the fastest non-strict program.<br />
<br />
However, the real and major advantage that non-strictness gives you over strict languages is you get to write cleaner and more composable code. In particular, you can separate ''production'' and ''consumption'' of data: don't know how many prime numbers you're going to need? Just make `primes` a list of ''all'' prime numbers, and then which ones actually get ''generated'' depends on how you use them in the rest of your code. By contrast, writing code in a strict language that constructs a data structure in response to demand usually will require first-class functions and/or a lot of manual hoop-jumping to make it all behave itself.<br />
<br />
Consider the following Haskell function definition:<br />
<br />
<haskell><br />
any :: (a -> Bool) -> [a] -> Bool<br />
any p = or . map p<br />
</haskell><br />
<br />
Because <tt>or</tt> uses non-strictness to stop at the first <tt>True</tt> in the input, <tt>map</tt> doesn't even need to know that only the first half of the list might be needed. We can write <tt>map</tt> in the completely straightforward and obviously correct way, and still have it interact well with <tt>or</tt> in this way; <tt>map</tt> produces data, <tt>or</tt> consumes it, and the two are properly decoupled.<br />
<br />
In a strict langauge, you'd have to write the recursion out manually:<br />
<br />
<haskell><br />
any p [] = False<br />
any p (x:xs)<br />
| p x = True<br />
| otherwise = any p xs<br />
</haskell><br />
<br />
since in strict languages only builtin control structures can decide whether some bit of code gets executed or not, ordinary functions like <tt>or</tt> can't.<br />
<br />
It's this additional power that Haskell has that leads people to say you can define your own control structures as normal Haskell functions, which allows all sorts of interesting patterns to be abstracted in an incredibly lightweight fashion. Labelled for-loops are a ''library'' in Haskell, rather than requiring special syntax and language support.<br />
<br />
=== How do I stop it? ===<br />
<br />
As mentioned above, non-strictness can hurt performance, e.g. if a result is definitely going to be needed later, you might as well evaluate it now, to avoid having to hold on to all the data that goes into it. Fortunately, the Haskell designers were aware of these problems and introduced a loophole or two so that we could force our programs to be strict when necessary: see [[Performance/Strictness]] and [[seq]].</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine/Non-strict_semantics&diff=56822User:Benmachine/Non-strict semantics2013-09-14T16:58:07Z<p>Benmachine: </p>
<hr />
<div>An expression language is said to have '''non-strict semantics''' if expressions can have a value even if some of their subexpressions do not. Haskell is one of the few modern languages to have non-strict semantics by default: nearly every other language has [[strict semantics]], in which if any subexpression fails to have a value, the whole expression fails with it.<br />
<br />
=== What? ===<br />
<br />
Any sufficiently capable programming language is ''non-total'', which is to say you can write expressions that do not produce a value: common examples are an exception thrown, an infinite loop, or unproductive recursion, e.g. the following definition in Haskell:<br />
<br />
<haskell><br />
noreturn :: Integer -> Integer<br />
noreturn x = negate (noreturn x)<br />
</haskell><br />
<br />
or the following Python function:<br />
<br />
def noreturn(x):<br />
while True:<br />
x = -x<br />
<br />
return x # not reached<br />
<br />
both fail to produce a value when executed. We say that <tt>noreturn x</tt> is undefined, and write <tt>noreturn x = [[Bottom|⊥]]</tt>.<br />
<br />
In Python the following expression to check if <tt>2</tt> is in some list:<br />
<br />
2 in [2,4,noreturn(5)]<br />
<br />
also fails to have a value, because in order to construct the list, the interpreter tries to work out <tt>noreturn(5)</tt>, which of course doesn't return a value. This is called '''innermost-first''' evaluation: in order to call a function with some arguments, you first have to calculate what all the arguments are, starting from the innermost function call and working outwards. The result is that Python is strict, in the sense that calling any function with an undefined argument produces an undefined value, i.e. <tt>f(⊥) = ⊥</tt>. If your language uses innermost-first evaluation, it correspondingly must have strict semantics.<br />
<br />
In Haskell, an analogous expression:<br />
<br />
<haskell><br />
elem 2 [2, 4, noreturn 5]<br />
</haskell><br />
<br />
in fact has the value <tt>True</tt>. The program does not have to compute <tt>noreturn 5</tt> because it is irrelevant to the overall value of the computation: only the values that are necessary to the result need be computed. This is called '''outermost-first''' evaluation because you first look at the outermost function call, <tt>elem</tt>, to see if it needs to use its arguments, and only if it does do you look at what those arguments are. This means that you can write a function that doesn't look at its argument, so it will return a value even if the argument is <tt>⊥</tt>. Such functions are not strict, i.e. they satisfy <tt>f(⊥) ≠ ⊥</tt>. Practically, this means that Haskell functions need not completely compute their arguments before using them, which is why e.g. <tt>take 3 [1..]</tt> can produce <tt>[1,2,3]</tt> even though it is given a conceptually infinite list.<br />
<br />
Note that outermost-first evaluation is not the only way to have non-strict semantics: a speculative evaluation strategy, that evaluated arguments in parallel with the function in case they were needed later, could also be non-strict, as long as whenever the speculative evaluation failed, the evaluation of the function continued.<br />
<br />
Note also that in order for a function to be truly non-strict, it must return something without inspecting its argument ''at all''. You might think that doesn't sound like a very useful function, but remember that it might be e.g. a partial application: the function <tt>(||) True</tt>, or equivalently <tt>\x -> True || x</tt> does not need to inspect its argument, since <tt>True || x</tt> is always <tt>True</tt>. There are other examples, too: constructors like <tt>Just</tt> wrap their argument without inspecting it, and some other functions apply constructors ''before'' looking at the argument, and hence still produce a partial result, e.g. <tt>inits ⊥ = [] : ⊥</tt><br />
<br />
=== Why? ===<br />
<br />
The important thing to understand about non-strict semantics is that it is not a performance feature. Non-strict semantics allows your language to only evaluate the things it needs to, but if you write your programs carefully, you'll only compute what is absolutely necessary ''anyway'', so the extra time your program spends working out what should and shouldn't be evaluated is time wasted. For this reason, a very well-optimised strict program will frequently outperform even the fastest non-strict program.<br />
<br />
However, the real and major advantage that non-strictness gives you over strict languages is you get to write cleaner and more composable code. In particular, you can separate ''production'' and ''consumption'' of data: don't know how many prime numbers you're going to need? Just make `primes` a list of ''all'' prime numbers, and then which ones actually get ''generated'' depends on how you use them in the rest of your code. By contrast, writing code in a strict language that constructs a data structure in response to demand usually will require first-class functions and/or a lot of manual hoop-jumping to make it all behave itself.<br />
<br />
Consider the following Haskell function definition:<br />
<br />
<haskell><br />
any :: (a -> Bool) -> [a] -> Bool<br />
any p = or . map p<br />
</haskell><br />
<br />
Because <tt>or</tt> uses non-strictness to stop at the first <tt>True</tt> in the input, <tt>map</tt> doesn't even need to know that only the first half of the list might be needed. We can write <tt>map</tt> in the completely straightforward and obviously correct way, and still have it interact well with <tt>or</tt> in this way; <tt>map</tt> produces data, <tt>or</tt> consumes it, and the two are properly decoupled.<br />
<br />
In a strict langauge, you'd have to write the recursion out manually:<br />
<br />
<haskell><br />
any p [] = False<br />
any p (x:xs)<br />
| p x = True<br />
| otherwise = any p xs<br />
</haskell><br />
<br />
since in strict languages only builtin control structures can decide whether some bit of code gets executed or not, ordinary functions like <tt>or</tt> can't.<br />
<br />
It's this additional power that Haskell has that leads people to say you can define your own control structures as normal Haskell functions, which allows all sorts of interesting patterns to be abstracted in an incredibly lightweight fashion. Labelled for-loops are a ''library'' in Haskell, rather than requiring special syntax and language support.<br />
<br />
=== How do I stop it? ===<br />
<br />
As mentioned above, non-strictness can hurt performance, e.g. if a result is definitely going to be needed later, you might as well evaluate it now, to avoid having to hold on to all the data that goes into it. Fortunately, the Haskell designers were aware of these problems and introduced a loophole or two so that we could force our programs to be strict when necessary: see [[Performance/Strictness]] and [[seq]].</div>Benmachinehttps://wiki.haskell.org/index.php?title=User:Benmachine/Non-strict_semantics&diff=55661User:Benmachine/Non-strict semantics2013-04-08T11:11:01Z<p>Benmachine: /* Why? */</p>
<hr />
<div>An expression language is said to have '''non-strict semantics''' if expressions can have a value even if some of their subexpressions do not. Haskell is one of the few modern languages to have non-strict semantics by default: nearly every other language has [[strict semantics]], in which if any subexpression fails to have a value, the whole expression fails with it.<br />
<br />
=== What? ===<br />
<br />
Any sufficiently capable programming language is ''non-total'', which is to say you can write expressions that do not produce a value: common examples are an exception thrown, an infinite loop, or unproductive recursion, e.g. the following definition in Haskell:<br />
<br />
<haskell><br />
noreturn :: Integer -> Integer<br />
noreturn x = negate (noreturn x)<br />
</haskell><br />
<br />
or the following Python function:<br />
<br />
def noreturn(x):<br />
while True:<br />
x = -x<br />
<br />
return x # not reached<br />
<br />
both fail to produce a value when executed. We say that <tt>noreturn x</tt> is undefined, and write <tt>noreturn x = [[Bottom|⊥]]</tt>.<br />
<br />
In Python the following expression to check if <tt>2</tt> is in some list:<br />
<br />
2 in [2,4,noreturn(5)]<br />
<br />
also fails to have a value, because in order to construct the list, the interpreter tries to work out <tt>noreturn(5)</tt>, which of course doesn't return a value. This is called '''innermost-first''' evaluation: in order to call a function with some arguments, you first have to calculate what all the arguments are, starting from the innermost function call and working outwards. The result is that Python is strict, in the sense that calling any function with an undefined argument produces an undefined value, i.e. <tt>f(⊥) = ⊥</tt>. If your language uses innermost-first evaluation, it correspondingly must have strict semantics.<br />
<br />
In Haskell, an analogous expression:<br />
<br />
<haskell><br />
elem 2 [2, 4, noreturn 5]<br />
</haskell><br />
<br />
in fact has the value <tt>True</tt>. The program does not try to compute <tt>noreturn 5</tt> because it is irrelevant to the overall value of the computation: only the values that are necessary to the result are computed. This is called '''outermost-first''' evaluation because you first look at the outermost function call, <tt>elem</tt>, to see if it needs to use its arguments, and only if it does do you look at what those arguments are. This means that you can write a function that doesn't look at its argument, so it will return a value even if the argument is <tt>⊥</tt>. Such functions are not strict, i.e. they satisfy <tt>f(⊥) ≠ ⊥</tt>. Practically, this means that Haskell functions need not completely compute their arguments before using them, which is why e.g. <tt>take 3 [1..]</tt> can produce <tt>[1,2,3]</tt> even though it is given a conceptually infinite list.<br />
<br />
Note that outermost-first evaluation is not the only way to have non-strict semantics: a speculative evaluation strategy, that evaluated arguments in parallel with the function in case they were needed later, could also be non-strict, as long as whenever the speculative evaluation failed, the evaluation of the function continued.<br />
<br />
Note also that in order for a function to be truly non-strict, it must return a result without inspecting its argument ''at all''. You might think that doesn't sound like a very useful function, but remember that it might be e.g. a partial application: the function <tt>(||) True</tt>, or equivalently <tt>\x -> True || x</tt> does not need to inspect its argument, since <tt>True || x</tt> is always <tt>True</tt>. There are other examples, too: constructors like <tt>Just</tt> wrap their argument without inspecting it, and some other functions apply constructors ''before'' looking at the argument, and hence still produce a partial result, e.g. <tt>inits ⊥ = [] : ⊥</tt><br />
<br />
=== Why? ===<br />
<br />
The important thing to understand about non-strict semantics is that it is not a performance feature. Non-strict semantics allows your language to only evaluate the things it needs to, but if you write your programs carefully, you'll only compute what is absolutely necessary ''anyway'', so the extra time your program spends working out what should and shouldn't be evaluated is time wasted. For this reason, a very well-optimised strict program will frequently outperform even the fastest non-strict program.<br />
<br />
However, the real and major advantage that non-strictness gives you over strict languages is you get to write cleaner and more composable code. In particular, you can separate ''production'' and ''consumption'' of data: don't know how many prime numbers you're going to need? Just make `primes` a list of ''all'' prime numbers, and then which ones actually get ''generated'' depends on how you use them in the rest of your code. By contrast, writing code in a strict language that constructs a data structure in response to demand usually will require first-class functions and/or a lot of manual hoop-jumping to make it all behave itself.<br />
<br />
Consider the following Haskell function definition:<br />
<br />
<haskell><br />
any :: (a -> Bool) -> [a] -> Bool<br />
any p = or . map p<br />
</haskell><br />
<br />
Because <tt>or</tt> uses non-strictness to stop at the first <tt>True</tt> in the input, <tt>map</tt> doesn't even need to know that only the first half of the list might be needed. We can write <tt>map</tt> in the completely straightforward and obviously correct way, and still have it interact well with <tt>or</tt> in this way; <tt>map</tt> produces data, <tt>or</tt> consumes it, and the two are properly decoupled.<br />
<br />
In a strict langauge, you'd have to write the recursion out manually:<br />
<br />
<haskell><br />
any p [] = False<br />
any p (x:xs)<br />
| p x = True<br />
| otherwise = any p xs<br />
</haskell><br />
<br />
since in strict languages only builtin control structures can decide whether some bit of code gets executed or not, ordinary functions like <tt>or</tt> can't.<br />
<br />
It's this additional power that Haskell has that leads people to say you can define your own control structures as normal Haskell functions, which allows all sorts of interesting patterns to be abstracted in an incredibly lightweight fashion. Labelled for-loops are a ''library'' in Haskell, rather than requiring special syntax and language support.<br />
<br />
=== How do I stop it? ===<br />
<br />
As mentioned above, non-strictness can hurt performance: if a result is definitely going to be needed later, you might as well evaluate it now, to avoid having to hold on to all the data that goes into it. Fortunately, the Haskell designers were aware of these problems and introduced a loophole or two so that we could force our programs to be strict when necessary: see [[Performance/Strictness]] and [[seq]].</div>Benmachinehttps://wiki.haskell.org/index.php?title=Impredicative_types&diff=55281Impredicative types2013-01-21T16:24:43Z<p>Benmachine: </p>
<hr />
<div>Impredicative types are an advanced form of polymorphism, to be contrasted with [[rank-N types]]. <br />
<br />
Standard Haskell allows polymorphic types via the use of type variables, which are understood to be ''universally quantified'': <tt>id :: a -> a</tt> means "''for all'' types <tt>a</tt>, <tt>id</tt> can take an argument and return a result of that type". All universal quantifiers ("for all"s) must appear at the beginning of a type.<br />
<br />
Higher-rank polymorphism (e.g. [[rank-N types]]) allows universal quantifiers to appear inside function types as well. It turns out that appearing to the right of function arrows is not interesting: <tt>Int -> forall a. a -> [a]</tt> is actually the same as <tt>forall a. Int -> a -> [a]</tt>. However, higher-rank polymorphism allows quantifiers to the ''left'' of function arrows, too, and <tt>(forall a. [a] -> Int) -> Int</tt> really ''is'' different from <tt>forall a. ([a] -> Int) -> Int</tt>.<br />
<br />
Impredicative types take this idea to its natural conclusion: universal quantifiers are allowed ''anywhere'' in a type, even inside normal datatypes like lists or <tt>Maybe</tt>. The GHC User's Guide gives the following example:<br />
<br />
<haskell><br />
f :: Maybe (forall a. [a] -> [a]) -> Maybe ([Int], [Char])<br />
f (Just g) = Just (g [3], g "hello")<br />
f Nothing = Nothing<br />
</haskell><br />
<br />
However, impredicative types do not mix very well with Haskell's type inference, so to actually use the above function with GHC 7.6.1 you need to specify the full (unpleasant) type signature for the <tt>Just</tt> constructor:<br />
<br />
<haskell><br />
ghci> f ((Just :: (forall a. [a] -> [a]) -> Maybe (forall a. [a] -> [a])) reverse)<br />
Just ([3],"olleh")<br />
</haskell><br />
<br />
Other examples are more successful: see below.<br />
<br />
=== See also ===<br />
<br />
* [http://www.haskell.org/ghc/docs/latest/html/users_guide/other-type-extensions.html#impredicative-polymorphism The GHC User's Guide on impredicative polymorphism].<br />
* [http://augustss.blogspot.co.uk/2011/07/impredicative-polymorphism-use-case-in.html A Pythonesque EDSL that makes use of impredicative polymorphism]<br />
* [http://stackoverflow.com/a/14065493/812053 A writeup of where ImpredicativePolymorphism is used in a GHC plugin to store a lookup table of strings to polymorphic functions]<br />
<br />
[[Category:Glossary]]</div>Benmachinehttps://wiki.haskell.org/index.php?title=Impredicative_types&diff=55220Impredicative types2013-01-04T16:43:18Z<p>Benmachine: Rewrite most of the article</p>
<hr />
<div>Impredicative types are an advanced form of polymorphism, to be contrasted with [[rank-N types]]. <br />
<br />
Standard Haskell allows polymorphic types via the use of type variables, which are understood to be ''universally quantified'': <tt>id :: a -> a</tt> means "''for all'' types <tt>a</tt>, <tt>id</tt> can take an argument and return a result of that type". All universal quantifiers ("for all"s) must appear at the beginning of a type.<br />
<br />
Higher-rank polymorphism (e.g. [[rank-N types]]) allows universal quantifiers to appear inside function types as well. It turns out that appearing to the right of function arrows is not interesting: <tt>Int -> forall a. a -> [a]</tt> is actually the same as <tt>forall a. Int -> a -> [a]</tt>. However, higher-rank polymorphism allows quantifiers to the ''left'' of function arrows, too, and <tt>(forall a. [a] -> Int) -> Int</tt> really ''is'' different from <tt>forall a. ([a] -> Int) -> Int</tt>.<br />
<br />
Impredicative types take this idea to its natural conclusion: universal quantifiers are allowed ''anywhere'' in a type, even inside normal datatypes like lists or <tt>Maybe</tt>. The GHC User's Guide gives the following example:<br />
<br />
<haskell><br />
f :: Maybe (forall a. [a] -> [a]) -> Maybe ([Int], [Char])<br />
f (Just g) = Just (g [3], g "hello")<br />
f Nothing = Nothing<br />
</haskell><br />
<br />
However, impredicative types do not mix very well with Haskell's type inference, so to actually use the above function with latest GHC you need to specify the full (unpleasant) type signature for the <tt>Just</tt> constructor:<br />
<br />
<haskell><br />
ghci> f ((Just :: (forall a. [a] -> [a]) -> Maybe (forall a. [a] -> [a])) reverse)<br />
Just ([3],"olleh")<br />
</haskell><br />
<br />
Other examples are more successful: see below.<br />
<br />
=== See also ===<br />
<br />
* [http://www.haskell.org/ghc/docs/latest/html/users_guide/other-type-extensions.html#impredicative-polymorphism The GHC User's Guide on impredicative polymorphism].<br />
* [http://augustss.blogspot.co.uk/2011/07/impredicative-polymorphism-use-case-in.html A Pythonesque EDSL that makes use of impredicative polymorphism]<br />
* [http://stackoverflow.com/a/14065493/812053 A writeup of where ImpredicativePolymorphism is used in a GHC plugin to store a lookup table of strings to polymorphic functions]<br />
<br />
[[Category:Glossary]]</div>Benmachinehttps://wiki.haskell.org/index.php?title=Impredicative_types&diff=55181Impredicative types2012-12-29T23:19:05Z<p>Benmachine: /* See also */</p>
<hr />
<div>Impredicative types are an advanced form of polymorphism, to be contrasted with [[rank-N types]].<br />
<br />
A standard Haskell type is universally quantified by default, and quantifiers can only appear at the top level of a type or to the right of function arrows.<br />
<br />
A higher-rank polymorphic type allows universal quantifiers to appear to the left of function arrows as well, so that function arguments can be functions that are themselves polymorphic.<br />
<br />
An impredicative type, on the other hand, allows universal quantifiers anywhere: in particular, may contain ordinary datatypes with polymorphic components. The GHC User's Guide gives the following example:<br />
<br />
<haskell><br />
f :: Maybe (forall a. [a] -> [a]) -> Maybe ([Int], [Char])<br />
f (Just g) = Just (g [3], g "hello")<br />
f Nothing = Nothing<br />
</haskell><br />
<br />
Impredicative types are enabled in GHC with the <hask>{-# LANGUAGE ImpredicativeTypes #-}</hask> pragma. They are among the less well-used and well-tested language extensions, and so some caution is advised in their use. <br />
<br />
=== See also ===<br />
<br />
* [http://www.haskell.org/ghc/docs/latest/html/users_guide/other-type-extensions.html#impredicative-polymorphism The GHC User's Guide on impredicative polymorphism].<br />
* [http://augustss.blogspot.co.uk/2011/07/impredicative-polymorphism-use-case-in.html A Pythonesque EDSL that makes use of impredicative polymorphism]<br />
* [http://stackoverflow.com/a/14065493/812053 A writeup of where ImpredicativePolymorphism is used in a GHC plugin to store a lookup table of strings to polymorphic functions]<br />
<br />
[[Category:Glossary]]</div>Benmachinehttps://wiki.haskell.org/index.php?title=Seq&diff=55175Seq2012-12-27T03:09:17Z<p>Benmachine: </p>
<hr />
<div><span>{{DISPLAYTITLE:seq}}</span><br />
<br />
The <tt>seq</tt> function is the most basic method of introducing strictness to a Haskell program. <tt>seq :: a -> b -> b</tt> takes two arguments of any type, and returns the second. However, it also has the important property that it is magically strict in its first argument. In essence, <tt>seq</tt> is defined by the following two equations:<br />
<br />
<haskell><br />
⊥ `seq` b = ⊥<br />
a `seq` b = b<br />
</haskell><br />
<br />
See [[Bottom]] for an explanation of the ⊥ symbol.<br />
<br />
A common misconception regarding <tt>seq</tt> is that <tt>seq x</tt> "evaluates" <tt>x</tt>. Well, sort of. <tt>seq</tt> doesn't evaluate anything just by virtue of existing in the source file, all it does is introduce an artificial data dependency of one value on another: when the result of <tt>seq</tt> is evaluated, the first argument must also (sort of; see below) be evaluated. As an example, suppose <tt>x :: Integer</tt>, then <tt>seq x b</tt> behaves essentially like <tt>if x == 0 then b else b</tt> – unconditionally equal to <tt>b</tt>, but forcing <tt>x</tt> along the way. In particular, the expression <tt>x `seq` x</tt> is completely redundant, and always has exactly the same effect as just writing <tt>x</tt>.<br />
<br />
Strictly speaking, the two equations of <tt>seq</tt> are all it must satisfy, and if the compiler can statically prove that the first argument is not ⊥, or that its second argument ''is'', it doesn't have to evaluate anything to meet its obligations. In practice, this almost never happens, and would probably be considered highly counterintuitive behaviour on the part of GHC (or whatever else you use to run your code). However, it ''is'' the case that evaluating <tt>b</tt> and ''then'' <tt>a</tt>, then returning <tt>b</tt> is a perfectly legitimate thing to do; it is to prevent this ambiguity that <tt>pseq</tt> was invented, but that's another story.<br />
<br />
=== Common uses of <tt>seq</tt> ===<br />
<br />
<tt>seq</tt> is typically used in the semantic interpretation of other strictness techniques, like strictness annotations in data types, or GHC's <tt>BangPatterns</tt> extension. For example, the meaning of this:<br />
<br />
<haskell><br />
f !x !y = z<br />
</haskell><br />
<br />
is this:<br />
<br />
<haskell><br />
f x y | x `seq` y `seq` False = undefined<br />
| otherwise = z<br />
</haskell><br />
<br />
although that literal translation may not actually take place.<br />
<br />
<tt>seq</tt> is frequently used with accumulating parameters to ensure that they don't become huge thunks, which will be forced at the end anyway. For example, strict foldl:<br />
<br />
<haskell><br />
foldl' :: (a -> b -> a) -> a -> [b] -> a<br />
foldl' _ z [] = z<br />
foldl' f z (x:xs) = let z' = f z x in z' `seq` foldl' f z' xs<br />
</haskell><br />
<br />
It's also used to define strict application:<br />
<br />
<haskell><br />
($!) :: (a -> b) -> a -> b<br />
f $! x = x `seq` f x<br />
</haskell><br />
<br />
which is useful for some of the same reasons.<br />
<br />
=== Controversy! ===<br />
<br />
Note that <tt>seq</tt> is the ''only'' way to force evaluation of a value with a function type (except by applying it, which is liable to cause other problems). As such, it is the only reason why Haskell programs are able to distinguish between the following two values:<br />
<br />
<haskell><br />
undefined :: a -> b<br />
const undefined :: a -> b<br />
</haskell><br />
<br />
This violates the principle from lambda calculus of extensionality of functions, or eta-conversion, because <tt>f</tt> and <tt>\x -> f x</tt> are distinct functions, even though they return the same output for ''every'' input. For this reason, <tt>seq</tt>, and this distinction, is sometimes ignored e.g. when assessing the correctness of [[Correctness of short cut fusion|optimisation techniques]] or type class instances.<br />
<br />
== See also ==<br />
<br />
* [http://stackoverflow.com/questions/12687392/why-is-seq-bad Why is seq bad?]<br />
<br />
[[Category:Glossary]]</div>Benmachinehttps://wiki.haskell.org/index.php?title=Seq&diff=55174Seq2012-12-27T02:54:19Z<p>Benmachine: unnecessary whitespace</p>
<hr />
<div><span>{{DISPLAYTITLE:seq}}</span><br />
<br />
The <tt>seq</tt> function is the most basic method of introducing strictness to a Haskell program. <tt>seq :: a -> b -> b</tt> takes two arguments of any type, and returns the second. However, it also has the important property that it is magically strict in its first argument. In essence, <tt>seq</tt> is defined by the following two equations:<br />
<br />
<haskell><br />
⊥ `seq` b = ⊥<br />
a `seq` b = b<br />
</haskell><br />
<br />
See [[Bottom]] for an explanation of the ⊥ symbol.<br />
<br />
A common misconception regarding <tt>seq</tt> is that <tt>seq x</tt> "evaluates" <tt>x</tt>. Well, sort of. <tt>seq</tt> doesn't evaluate anything just by virtue of existing in the source file, all it does is introduce an artificial data dependency of one value on another: when the result of <tt>seq</tt> is evaluated, the first argument must also be evaluated. As an example, suppose <tt>x :: Integer</tt>, then <tt>seq x b</tt> behaves essentially like <tt>if x == 0 then b else b</tt> – unconditionally equal to <tt>b</tt>, but forcing <tt>x</tt> along the way. In particular, the expression <tt>x `seq` x</tt> is completely redundant, and always has exactly the same effect as just writing <tt>x</tt>.<br />
<br />
Strictly speaking, the two equations of <tt>seq</tt> are all it must satisfy, and if the compiler can statically prove that the first argument is not ⊥, it doesn't have to evaluate it to meet its obligations. In practice, this almost never happens, and would probably be considered highly counterintuitive behaviour on the part of GHC (or whatever else you use to run your code). However, it ''is'' the case that evaluating <tt>b</tt> and ''then'' <tt>a</tt>, then returning <tt>b</tt> is a perfectly legitimate thing to do; it is to prevent this ambiguity that <tt>pseq</tt> was invented, but that's another story.<br />
<br />
=== Common uses of <tt>seq</tt> ===<br />
<br />
<tt>seq</tt> is typically used in the semantic interpretation of other strictness techniques, like strictness annotations in data types, or GHC's <tt>BangPatterns</tt> extension. For example, the meaning of this:<br />
<br />
<haskell><br />
f !x !y = z<br />
</haskell><br />
<br />
is this:<br />
<br />
<haskell><br />
f x y | x `seq` y `seq` False = undefined<br />
| otherwise = z<br />
</haskell><br />
<br />
although that literal translation may not actually take place.<br />
<br />
<tt>seq</tt> is frequently used with accumulating parameters to ensure that they don't become huge thunks, which will be forced at the end anyway. For example, strict foldl:<br />
<br />
<haskell><br />
foldl' :: (a -> b -> a) -> a -> [b] -> a<br />
foldl' _ z [] = z<br />
foldl' f z (x:xs) = let z' = f z x in z' `seq` foldl' f z' xs<br />
</haskell><br />
<br />
It's also used to define strict application:<br />
<br />
<haskell><br />
($!) :: (a -> b) -> a -> b<br />
f $! x = x `seq` f x<br />
</haskell><br />
<br />
which is useful for some of the same reasons.<br />
<br />
=== Controversy! ===<br />
<br />
Note that <tt>seq</tt> is the ''only'' way to force evaluation of a value with a function type (except by applying it, which is liable to cause other problems). As such, it is the only reason why Haskell programs are able to distinguish between the following two values:<br />
<br />
<haskell><br />
undefined :: a -> b<br />
const undefined :: a -> b<br />
</haskell><br />
<br />
This violates the principle from lambda calculus of extensionality of functions, or eta-conversion, because <tt>f</tt> and <tt>\x -> f x</tt> are distinct functions, even though they return the same output for ''every'' input. For this reason, <tt>seq</tt>, and this distinction, is sometimes ignored e.g. when assessing the correctness of [[Correctness of short cut fusion|optimisation techniques]] or type class instances.<br />
<br />
== See also ==<br />
<br />
* [http://stackoverflow.com/questions/12687392/why-is-seq-bad Why is seq bad?]<br />
<br />
[[Category:Glossary]]</div>Benmachinehttps://wiki.haskell.org/index.php?title=Talk:Functional_dependencies&diff=55172Talk:Functional dependencies2012-12-27T02:48:15Z<p>Benmachine: Talk:Functional dependency moved to Talk:Functional dependencies: More often referred to in plural (e.g. extension name)</p>
<hr />
<div>This page was moved from [[Functional dependencies]], but I think it's more natural there - the extension is in the plural and they are usually referred to in plural. I think it should be moved back.</div>Benmachinehttps://wiki.haskell.org/index.php?title=Talk:Functional_dependency&diff=55173Talk:Functional dependency2012-12-27T02:48:15Z<p>Benmachine: Talk:Functional dependency moved to Talk:Functional dependencies: More often referred to in plural (e.g. extension name)</p>
<hr />
<div>#REDIRECT [[Talk:Functional dependencies]]</div>Benmachinehttps://wiki.haskell.org/index.php?title=Functional_dependencies&diff=55170Functional dependencies2012-12-27T02:48:13Z<p>Benmachine: Functional dependency moved to Functional dependencies over redirect: More often referred to in plural (e.g. extension name)</p>
<hr />
<div>[[Category:Glossary]]<br />
[[Category:Language extensions]]<br />
Functional dependencies are used to constrain the parameters of type classes. They let you state that in a [[multi-parameter type class]], one of the [[parameter]]s can be determined from the others, so that the [[parameter]] determined by the others can, for example, be the return type but none of the argument types of some of the methods.<br />
<br />
==Examples==<br />
Suppose you want to implement some code to perform simple [[linear algebra]]:<br />
<haskell><br />
data Vector = Vector Int Int deriving (Eq, Show)<br />
data Matrix = Matrix Vector Vector deriving (Eq, Show)<br />
</haskell><br />
You want these to behave as much like numbers as possible. So you might start by overloading Haskell's Num class:<br />
<haskell><br />
instance Num Vector where<br />
Vector a1 b1 + Vector a2 b2 = Vector (a1+a2) (b1+b2)<br />
Vector a1 b1 - Vector a2 b2 = Vector (a1-a2) (b1-b2)<br />
{- ... and so on ... -}<br />
<br />
instance Num Matrix where<br />
Matrix a1 b1 + Matrix a2 b2 = Matrix (a1+a2) (b1+b2)<br />
Matrix a1 b1 - Matrix a2 b2 = Matrix (a1-a2) (b1-b2)<br />
{- ... and so on ... -}<br />
</haskell><br />
The problem comes when you want to start multiplying quantities. You really need a multiplication function which overloads to different types:<br />
<haskell><br />
(*) :: Matrix -> Matrix -> Matrix<br />
(*) :: Matrix -> Vector -> Vector<br />
(*) :: Matrix -> Int -> Matrix<br />
(*) :: Int -> Matrix -> Matrix<br />
{- ... and so on ... -}<br />
</haskell><br />
How do we specify a type class which allows all these possibilities?<br />
<br />
We could try this:<br />
<haskell><br />
class Mult a b c where<br />
(*) :: a -> b -> c<br />
<br />
instance Mult Matrix Matrix Matrix where<br />
{- ... -}<br />
<br />
instance Mult Matrix Vector Vector where<br />
{- ... -}<br />
</haskell><br />
That, however, isn't really what we want. As it stands, even a simple expression like this has an ambiguous type unless you supply an additional type declaration on the intermediate expression:<br />
<haskell><br />
m1, m2, m3 :: Matrix<br />
(m1 * m2) * m3 -- type error; type of (m1*m2) is ambiguous<br />
(m1 * m2) :: Matrix * m3 -- this is ok<br />
</haskell><br />
After all, nothing is stopping someone from coming along later and adding another instance:<br />
<haskell><br />
instance Mult Matrix Matrix (Maybe Char) where<br />
{- whatever -}<br />
</haskell><br />
The problem is that <hask>c</hask> shouldn't really be a free type variable. When you know the types of the things that you're multiplying, the result type should be determined from that information alone.<br />
<br />
You can express this by specifying a functional dependency, or fundep for short:<br />
<haskell><br />
class Mult a b c | a b -> c where<br />
(*) :: a -> b -> c<br />
</haskell><br />
This tells Haskell that <hask>c</hask> is uniquely determined from <hask>a</hask> and <hask>b</hask>.<br />
<br />
Fundeps have lots more uses than just implementing C++-style function overloading, of course. See [http://web.cecs.pdx.edu/~mpj/pubs/fundeps.html the paper] by Mark P. Jones for further details.<br />
<br />
Fundeps are not standard Haskell 98. (Nor are [[multi-parameter type class]]es, for that matter.) They are, however, supported at least in [[GHC]] and [[Hugs]] and will almost certainly end up in Haskell'.<br />
<br />
[[User:AndrewBromage]]<br />
<br />
== Another example ==<br />
<br />
The following example makes use of the FlexibleInstances, MultiParamTypeClasses and FunctionalDependencies GHC extensions.<br />
<br />
<haskell><br />
-- Read as: "container" type determines "elem" type.<br />
class Extract container elem | container -> elem where<br />
extract :: container -> elem<br />
</haskell><br />
<br />
The functional dependency "container -> elem" promises that we won't declare multiple instances with the same "container" type.<br />
<br />
<haskell><br />
instance Extract (a,b) a where<br />
extract (x,_) = x<br />
</haskell><br />
<br />
Because of the functional dependency we can't have the previous instance *and* this one:<br />
<br />
<haskell>-- instance Extract (a,b) b where ...</haskell><br />
<br />
Because of the functional dependency we can say:<br />
<br />
<haskell>v = extract ('x', 3)</haskell><br />
<br />
and it will infer the type <haskell>v :: Char</haskell><br />
<br />
Without the functional dependency, both instances above would be allowed, and the type of v would be potentially ambiguous. Even if only one instance is defined, the type system will not figure it out without the functional dependency.<br />
<br />
== Tutorials ==<br />
<br />
* [http://www.cs.chalmers.se/~hallgren/Papers/wm01.html Fun with functional dependencies], Thomas Hallgren (2001)<br />
* [[User:ConradParker/InstantInsanity | Type-Level Instant Insanity]], Conrad Parker (2007)<br />
<br />
== See also ==<br />
* [http://www.haskell.org/ghc/docs/latest/html/users_guide/type-class-extensions.html#functional-dependencies GHC documentation]</div>Benmachinehttps://wiki.haskell.org/index.php?title=Functional_dependency&diff=55171Functional dependency2012-12-27T02:48:13Z<p>Benmachine: Functional dependency moved to Functional dependencies over redirect: More often referred to in plural (e.g. extension name)</p>
<hr />
<div>#REDIRECT [[Functional dependencies]]</div>Benmachine