https://wiki.haskell.org/api.php?action=feedcontributions&user=Mnislaih&feedformat=atomHaskellWiki - User contributions [en]2024-03-19T13:53:26ZUser contributionsMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=Failure&diff=32052Failure2009-12-01T13:22:31Z<p>Mnislaih: </p>
<hr />
<div>= Exceptions, errors, failures oh my! =<br />
<br />
Terminology is a little confusing. There's a few different things floating around:<br />
<br />
* Error usually refers to a programming error. It can also refer to the "error" function, which in fact causes a runtime exception to be triggered.<br />
* Exception usually refers to an exception which is thrown in the IO monad. It can also refer to the actually typeclass "Exception" which was introduced along with extensible exceptions.<br />
* Fail is referring to the "fail" function, which is part of the Monad typeclass and is almost universally despised.<br />
<br />
To avoid the baggage and name clashes introduced with all of the above, we use the term failure. This name is used consistently for module names, type classes, function names and the abstract concept.<br />
<br />
But what is a failure? It's any time that something does not succeed. Of course, this depends on your definition of success. Here are some examples:<br />
<br />
* readInt fails when it receives invalid input.<br />
* head fails when it receives an empty list.<br />
* lookup fails when the key is not find in the list.<br />
* at (also known as !!) fails when the index is past the end of the list.<br />
<br />
Now that we know what a failure is, let's discuss how to deal with it.<br />
<br />
= Prior Art =<br />
<br />
There are currently a number of methods available for dealing with failures. However, all of them are lacking in some way:<br />
<br />
* Maybe. However, there's no information on *what* failed.<br />
* The error function. But not all failures should be fatal.<br />
* IO exceptions. But they force your code into your IO monad, plus it's non-obvious that a function might fail with an exception based solely on its return type.<br />
* Custom error values. But how do you compose two libraries together?<br />
* The Either/ErrorT monads. Apart from the fact that Either is not a Monad by default (you can use the mtl or transformers instances, but that introduces undesirable orphan instances), the main problem with these lies in composability and extensibility.<br />
<br />
This abundance of error handling methods leads to lots of gluing code when combining libraries which use different notions of failure. <br />
Examples:<br />
<br />
* The partial functions in the Prelude and other base modules, such as head, tail, fromJust, lookup, etc. use the error function.<br />
* parsec models failure using Either ParseError<br />
* http models failure using Either ConnError<br />
* The HDBC package models failure using the SQLError exception<br />
* The cgi package uses exceptions<br />
<br />
Quoting from Eric Kidd:<br />
{| class="wikitable"<br />
|-<br />
|<br />
<pre><br />
Consider a program to download a web page and parse it:<br />
<br />
1. Network.URI.parseURI returns (Maybe URI).<br />
2. Network.HTTP.simpleHTTP returns (IO (Result Request)), which is basically a broken version of (IO (Either ConnError Request)).<br />
3. Parsec returns (Either ParseError a)<br />
<br />
So there's no hope that I can write anything like:<br />
<br />
do uri <- parseURI uriStr<br />
doc <- evenSimplerHTTP uri<br />
parsed <- parse grammar uriStr doc<br />
</pre><br />
|}<br />
<br />
= Enter control-monad-failure, stage left =<br />
<br />
What we want is an abstract notion of failure which does not tie us to any particular error handling mechanism. This is what the [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/control-monad-failure control-monad-failure] package intents to provide. <br />
<br />
MonadFailure is the typeclass used to model this abstract notion of failure. It lives in the Control.Monad.Failure module and consists entirely of the following two lines:<br />
<br />
class Monad m => MonadFailure e m where<br />
failure :: e -> m a<br />
<br />
So now, you could define a safe head function as follows:<br />
<br />
data EmptyListFailure = EmptyListFailure<br />
head :: MonadFailure EmptyListFailure m => [a] -> m a<br />
head [] = failure EmptyListFailure<br />
head (x:_) = return x<br />
<br />
Notice how the opposite of failure is "return".<br />
<br />
== Handling failures ==<br />
<br />
Each of the mentioned error handling mechanisms is equipped with a primitive for handling a failure.<br />
When dealing with a failure, it's obvious based on the type signature what might go wrong. In the example of head above, obviously head will fail if the list is empty.<br />
<br />
In any event, we need to instantiate MonadFailure in order to actually call the head function. The control-monad-failure package comes with instances for each of the mentioned error handling mechanisms.<br />
<br />
* Maybe. failure == Nothing<br />
* List. failure == []<br />
* IO. failure == throw<br />
* Either. failure == Left<br />
* ErrorT (provided by mtl or transformers). failure == throwError.<br />
<br />
However, there are also two other packages available which provide more resilient options.<br />
<br />
=== [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/control-monad-exception control-monad-exception ]===<br />
<br />
c-m-e provides a EM monad for explicitly typed, checked exceptions a la Java.<br />
The type of a EM computation carries the list of exceptions it can throw in its type. For example, let's say that we have a basic arithmetic expression evaluator which can throw divide by zero or sum overflow exceptions. Its type will be:<br />
<br />
eval :: (Throws DivByZero l, Throws SumOverflow l) => Expr -> EM l Double<br />
<br />
Correspondingly, a computation which calls eval and handles only the DivByZero exception gets the type:<br />
<br />
:t eval <expr> `catch` \DivByZero -> return 0<br />
eval <expr> :: Throws SumOverflow l => EM l Double<br />
<br />
<br />
=== [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/attempt attempt] ===<br />
<br />
Attempt is intended when you don't know what might go wrong, but you know it could happen. For example, let's say I want to define a type class:<br />
<br />
class Convert a b where<br />
convert :: a -> Attempt b<br />
<br />
Other libraries may want to instantiate Convert for their own types. However, when writing the Convert typeclass, I don't know exactly what failures may occur. When writing the "Convert String Int" instances, it might be InvalidInteger. But when writing the "Convert English Spanish" typeclass (hey, it could happen) it might be InvalidGrammar.<br />
<br />
= [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/safe-failure safe-failure] =<br />
<br />
[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/safe-failure safe-failure] is a collection of functions from the Prelude which return values in some MonadFailure monad. It provides all the functions available in Neil Mitchell's safe package, plus a few extra.<br />
<br />
= Stack traces =<br />
<br />
As an added bonus, both control-monad-exception and attempt provide stack traces, or more exactly [http://pepeiborra.posterous.com/monadic-stack-traces-that-make-a-lot-of-sense monadic call traces], via [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/monadloc MonadLoc].<br />
<br />
= References =<br />
<br />
* http://www.randomhacks.net/articles/2007/03/10/haskell-8-ways-to-report-errors<br />
* http://www.haskell.org/pipermail/libraries/2007-March/007010.html</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Failure&diff=31473Failure2009-11-08T01:42:59Z<p>Mnislaih: </p>
<hr />
<div>This page discusses the not-yet-released control-monad-failure package and its associated packages. As of this writing (November 7, 2009), the packages are expected to be released within the next week.<br />
<br />
= Exceptions, errors, failures oh my! =<br />
<br />
Terminology is a little confusing. There's a few different things floating around:<br />
<br />
* Error usually refers to a programming error. It can also refer to the "error" function, which in fact causes a runtime exception to be triggered.<br />
* Exception usually refers to an exception which is thrown in the IO monad. It can also refer to the actually typeclass "Exception" which was introduced along with extensible exceptions.<br />
* Fail is referring to the "fail" function, which is part of the Monad typeclass and is almost universally despised.<br />
<br />
To avoid the baggage and name clashes introduced with all of the above, we use the term failure. This name is used consistently for module names, type classes, function names and the abstract concept.<br />
<br />
But what is a failure? It's any time that something does not succeed. Of course, this depends on your definition of success. Here are some examples:<br />
<br />
* readInt fails when it receives invalid input.<br />
* head fails when it receives an empty list.<br />
* lookup fails when the key is not find in the list.<br />
* at (also known as !!) fails when the index is past the end of the list.<br />
<br />
Now that we know what a failure is, let's discuss how to deal with it.<br />
<br />
= Prior Art =<br />
<br />
There are currently a number of methods available for dealing with failures. However, all of them are lacking in some way:<br />
<br />
* Maybe. However, there's no information on *what* failed.<br />
* The error function. But not all failures should be fatal.<br />
* IO exceptions. But they force your code into your IO monad, plus it's non-obvious that a function might fail with an exception based solely on its return type.<br />
* Custom error values. But how do you compose two libraries together?<br />
* The Either/ErrorT monads. Apart from the fact that Either is not a Monad by default (you can use the mtl or transformers instances, but that introduces undesirable orphan instances), the main problem with these lies in composability and extensibility.<br />
<br />
This abundance of error handling methods leads to lots of gluing code when combining libraries which use different notions of failure. <br />
Examples:<br />
<br />
* The partial functions in the Prelude and other base modules, such as head, tail, fromJust, lookup, etc. use the error function.<br />
* parsec models failure using Either ParseError<br />
* http models failure using Either ConnError<br />
* The HDBC package models failure using the SQLError exception<br />
* The cgi package uses exceptions<br />
<br />
Quoting from Eric Kidd:<br />
{| class="wikitable"<br />
|-<br />
|<br />
<pre><br />
Consider a program to download a web page and parse it:<br />
<br />
1. Network.URI.parseURI returns (Maybe URI).<br />
2. Network.HTTP.simpleHTTP returns (IO (Result Request)), which is basically a broken version of (IO (Either ConnError Request)).<br />
3. Parsec returns (Either ParseError a)<br />
<br />
So there's no hope that I can write anything like:<br />
<br />
do uri <- parseURI uriStr<br />
doc <- evenSimplerHTTP uri<br />
parsed <- parse grammar uriStr doc<br />
</pre><br />
|}<br />
<br />
= Enter control-monad-failure, stage left =<br />
<br />
What we want is an abstract notion of failure which does not tie us to any particular error handling mechanism. This is what the [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/control-monad-failure control-monad-failure] package intents to provide. <br />
<br />
MonadFailure is the typeclass used to model this abstract notion of failure. It lives in the Control.Monad.Failure module and consists entirely of the following two lines:<br />
<br />
class Monad m => MonadFailure e m where<br />
failure :: e -> m a<br />
<br />
So now, you could define a safe head function as follows:<br />
<br />
data EmptyListFailure = EmptyListFailure<br />
head :: MonadFailure EmptyListFailure m => [a] -> m a<br />
head [] = failure EmptyListFailure<br />
head (x:_) = return x<br />
<br />
Notice how the opposite of failure is "return".<br />
<br />
== Handling failures ==<br />
<br />
Each of the mentioned error handling mechanisms is equipped with a primitive for handling a failure.<br />
When dealing with a failure, it's obvious based on the type signature what might go wrong. In the example of head above, obviously head will fail if the list is empty.<br />
<br />
In any event, we need to instantiate MonadFailure in order to actually call the head function. The control-monad-failure package comes with instances for each of the mentioned error handling mechanisms.<br />
<br />
* Maybe. failure == Nothing<br />
* List. failure == []<br />
* IO. failure == throw<br />
* Either. failure == Left<br />
* ErrorT (provided by mtl or transformers). failure == throwError.<br />
<br />
However, there are also two other packages available which provide more resilient options.<br />
<br />
=== [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/control-monad-exception control-monad-exception ]===<br />
<br />
c-m-e provides a EM monad for explicitly typed, checked exceptions a la Java.<br />
The type of a EM computation carries the list of exceptions it can throw in its type. For example, let's say that we have a basic arithmetic expression evaluator which can throw divide by zero or sum overflow exceptions. Its type will be:<br />
<br />
eval :: (Throws DivByZero l, Throws SumOverflow l) => Expr -> EM l Double<br />
<br />
Correspondingly, a computation which calls eval and handles only the DivByZero exception gets the type:<br />
<br />
:t eval <expr> `catch` \DivByZero -> return 0<br />
eval <expr> :: Throws SumOverflow l => EM l Double<br />
<br />
<br />
=== [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/attempt attempt] ===<br />
<br />
Attempt is intended when you don't know what might go wrong, but you know it could happen. For example, let's say I want to define a type class:<br />
<br />
class Convert a b where<br />
convert :: a -> Attempt b<br />
<br />
Other libraries may want to instantiate Convert for their own types. However, when writing the Convert typeclass, I don't know exactly what failures may occur. When writing the "Convert String Int" instances, it might be InvalidInteger. But when writing the "Convert English Spanish" typeclass (hey, it could happen) it might be InvalidGrammar.<br />
<br />
= [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/safe-failure safe-failure] =<br />
<br />
[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/safe-failure safe-failure] is a collection of functions from the Prelude which return values in the MonadFailure monad. It provides all the functions available in Neil Mitchell's safe package, plus a few extra.<br />
<br />
= Stack traces =<br />
<br />
As an added bonus, both control-monad-exception and attempt provide stack traces, or more exactly [http://pepeiborra.posterous.com/monadic-stack-traces-that-make-a-lot-of-sense monadic call traces], via [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/monadloc MonadLoc].<br />
<br />
= References =<br />
<br />
* http://www.randomhacks.net/articles/2007/03/10/haskell-8-ways-to-report-errors<br />
* http://www.haskell.org/pipermail/libraries/2007-March/007010.html</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Failure&diff=31472Failure2009-11-08T01:42:22Z<p>Mnislaih: </p>
<hr />
<div>This page discusses the not-yet-released control-monad-failure package and its associated packages. As of this writing (November 7, 2009), the packages are expected to be released within the next week.<br />
<br />
= Exceptions, errors, failures oh my! =<br />
<br />
Terminology is a little confusing. There's a few different things floating around:<br />
<br />
* Error usually refers to a programming error. It can also refer to the "error" function, which in fact causes a runtime exception to be triggered.<br />
* Exception usually refers to an exception which is thrown in the IO monad. It can also refer to the actually typeclass "Exception" which was introduced along with extensible exceptions.<br />
* Fail is referring to the "fail" function, which is part of the Monad typeclass and is almost universally despised.<br />
<br />
To avoid the baggage and name clashes introduced with all of the above, we use the term failure. This name is used consistently for module names, type classes, function names and the abstract concept.<br />
<br />
But what is a failure? It's any time that something does not succeed. Of course, this depends on your definition of success. Here are some examples:<br />
<br />
* readInt fails when it receives invalid input.<br />
* head fails when it receives an empty list.<br />
* lookup fails when the key is not find in the list.<br />
* at (also known as !!) fails when the index is past the end of the list.<br />
<br />
Now that we know what a failure is, let's discuss how to deal with it.<br />
<br />
= Prior Art =<br />
<br />
There are currently a number of methods available for dealing with failures. However, all of them are lacking in some way:<br />
<br />
* Maybe. However, there's no information on *what* failed.<br />
* The error function. But not all failures should be fatal.<br />
* IO exceptions. But they force your code into your IO monad, plus it's non-obvious that a function might fail with an exception based solely on its return type.<br />
* Custom error values. But how do you compose two libraries together?<br />
* The Either/ErrorT monads. Apart from the fact that Either is not a Monad by default (you can use the mtl or transformers instances, but that introduces undesirable orphan instances), the main problem with these lies in composability and extensibility.<br />
<br />
This abundance of error handling methods leads to lots of gluing code when combining libraries which use different notions of failure. <br />
Examples:<br />
<br />
* The partial functions in the Prelude and other base modules, such as head, tail, fromJust, lookup, etc. use the error function.<br />
* parsec models failure using Either ParseError<br />
* http models failure using Either ConnError<br />
* The HDBC package models failure using the SQLError exception<br />
* The cgi package uses exceptions<br />
<br />
Quoting from Eric Kidd:<br />
{| class="wikitable"<br />
|-<br />
|<br />
<pre><br />
Consider a program to download a web page and parse it:<br />
<br />
1. Network.URI.parseURI returns (Maybe URI).<br />
2. Network.HTTP.simpleHTTP returns (IO (Result Request)), which is basically a broken version of (IO (Either ConnError Request)).<br />
3. Parsec returns (Either ParseError a)<br />
<br />
So there's no hope that I can write anything like:<br />
<br />
do uri <- parseURI uriStr<br />
doc <- evenSimplerHTTP uri<br />
parsed <- parse grammar uriStr doc<br />
</pre><br />
|}<br />
<br />
= Enter control-monad-failure, stage left =<br />
<br />
What we want is an abstract notion of failure which does not tie us to any particular error handling mechanism. This is what the [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/control-monad-failure control-monad-failure] package intents to provide. <br />
<br />
MonadFailure is the typeclass used to model this abstract notion of failure. It lives in the Control.Monad.Failure module and consists entirely of the following two lines:<br />
<br />
class Monad m => MonadFailure e m where<br />
failure :: e -> m a<br />
<br />
So now, you could define a safe head function as follows:<br />
<br />
data EmptyListFailure = EmptyListFailure<br />
head :: MonadFailure EmptyListFailure m => [a] -> m a<br />
head [] = failure EmptyListFailure<br />
head (x:_) = return x<br />
<br />
Notice how the opposite of failure is "return".<br />
<br />
== Handling failures ==<br />
<br />
Each of the mentioned error handling mechanisms is equipped with a primitive for handling a failure.<br />
When dealing with a failure, it's obvious based on the type signature what might go wrong. In the example of head above, obviously head will fail if the list is empty.<br />
<br />
In any event, we need to instantiate MonadFailure in order to actually call the head function. The control-monad-failure package comes with instances for each of the mentioned error handling mechanisms.<br />
<br />
* Maybe. failure == Nothing<br />
* List. failure == []<br />
* IO. failure == throw<br />
* Either. failure == Left<br />
* ErrorT (provided by mtl or transformers). failure == throwError.<br />
<br />
However, there are also two other packages available which provide more resilient options.<br />
<br />
=== [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/control-monad-exception control-monad-exception ]===<br />
<br />
c-m-e provides a EM monad for explicitly typed, checked exceptions a la Java.<br />
The type of a EM computation carries the list of exceptions it can throw in its type. For example, let's say that we have a basic arithmetic expression evaluator which can throw divide by zero or sum overflow exceptions. Its type will be:<br />
<br />
eval :: (Throws DivByZero l, Throws SumOverflow l) => Expr -> EM l Double<br />
<br />
Correspondingly, a computation which calls eval and handles only the DivByZero exception gets the type:<br />
<br />
:t eval <expr> `catch` \DivByZero -> return 0<br />
eval <expr> :: Throws SumOverflow l => EM l Double<br />
<br />
<br />
=== [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/attempt attempt] ===<br />
<br />
Attempt is intended when you don't know what might go wrong, but you know it could happen. For example, let's say I want to define a type class:<br />
<br />
class Convert a b where<br />
convert :: a -> Attempt b<br />
<br />
Other libraries may want to instantiate Convert for their own types. However, when writing the Convert typeclass, I don't know exactly what failures may occur. When writing the "Convert String Int" instances, it might be InvalidInteger. But when writing the "Convert English Spanish" typeclass (hey, it could happen) it might be InvalidGrammar.<br />
<br />
= [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/safe-failure safe-failure] =<br />
<br />
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/safe-failure safe-failure] is a collection of functions from the Prelude which return values in the MonadFailure monad. It provides all the functions available in Neil Mitchell's safe package, plus a few extra.<br />
<br />
= Stack traces =<br />
<br />
As an added bonus, both control-monad-exception and attempt provide stack traces, or more exactly [http://pepeiborra.posterous.com/monadic-stack-traces-that-make-a-lot-of-sense monadic call traces], via [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/monadloc MonadLoc].<br />
<br />
= References =<br />
<br />
* http://www.randomhacks.net/articles/2007/03/10/haskell-8-ways-to-report-errors<br />
* http://www.haskell.org/pipermail/libraries/2007-March/007010.html</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Failure&diff=31471Failure2009-11-08T01:41:56Z<p>Mnislaih: </p>
<hr />
<div>This page discusses the not-yet-released control-monad-failure package and its associated packages. As of this writing (November 7, 2009), the packages are expected to be released within the next week.<br />
<br />
= Exceptions, errors, failures oh my! =<br />
<br />
Terminology is a little confusing. There's a few different things floating around:<br />
<br />
* Error usually refers to a programming error. It can also refer to the "error" function, which in fact causes a runtime exception to be triggered.<br />
* Exception usually refers to an exception which is thrown in the IO monad. It can also refer to the actually typeclass "Exception" which was introduced along with extensible exceptions.<br />
* Fail is referring to the "fail" function, which is part of the Monad typeclass and is almost universally despised.<br />
<br />
To avoid the baggage and name clashes introduced with all of the above, we use the term failure. This name is used consistently for module names, type classes, function names and the abstract concept.<br />
<br />
But what is a failure? It's any time that something does not succeed. Of course, this depends on your definition of success. Here are some examples:<br />
<br />
* readInt fails when it receives invalid input.<br />
* head fails when it receives an empty list.<br />
* lookup fails when the key is not find in the list.<br />
* at (also known as !!) fails when the index is past the end of the list.<br />
<br />
Now that we know what a failure is, let's discuss how to deal with it.<br />
<br />
= Prior Art =<br />
<br />
There are currently a number of methods available for dealing with failures. However, all of them are lacking in some way:<br />
<br />
* Maybe. However, there's no information on *what* failed.<br />
* The error function. But not all failures should be fatal.<br />
* IO exceptions. But they force your code into your IO monad, plus it's non-obvious that a function might fail with an exception based solely on its return type.<br />
* Custom error values. But how do you compose two libraries together?<br />
* The Either/ErrorT monads. Apart from the fact that Either is not a Monad by default (you can use the mtl or transformers instances, but that introduces undesirable orphan instances), the main problem with these lies in composability and extensibility.<br />
<br />
This abundance of error handling methods leads to lots of gluing code when combining libraries which use different notions of failure. <br />
Examples:<br />
<br />
* The partial functions in the Prelude and other base modules, such as head, tail, fromJust, lookup, etc. use the error function.<br />
* parsec models failure using Either ParseError<br />
* http models failure using Either ConnError<br />
* The HDBC package models failure using the SQLError exception<br />
* The cgi package uses exceptions<br />
<br />
Quoting from Eric Kidd:<br />
{| class="wikitable"<br />
|-<br />
|<br />
<pre><br />
Consider a program to download a web page and parse it:<br />
<br />
1. Network.URI.parseURI returns (Maybe URI).<br />
2. Network.HTTP.simpleHTTP returns (IO (Result Request)), which is basically a broken version of (IO (Either ConnError Request)).<br />
3. Parsec returns (Either ParseError a)<br />
<br />
So there's no hope that I can write anything like:<br />
<br />
do uri <- parseURI uriStr<br />
doc <- evenSimplerHTTP uri<br />
parsed <- parse grammar uriStr doc<br />
</pre><br />
|}<br />
<br />
= Enter control-monad-failure, stage left =<br />
<br />
What we want is an abstract notion of failure which does not tie us to any particular error handling mechanism. This is what the [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/control-monad-failure control-monad-failure] package intents to provide. <br />
<br />
MonadFailure is the typeclass used to model this abstract notion of failure. It lives in the Control.Monad.Failure module and consists entirely of the following two lines:<br />
<br />
class Monad m => MonadFailure e m where<br />
failure :: e -> m a<br />
<br />
So now, you could define a safe head function as follows:<br />
<br />
data EmptyListFailure = EmptyListFailure<br />
head :: MonadFailure EmptyListFailure m => [a] -> m a<br />
head [] = failure EmptyListFailure<br />
head (x:_) = return x<br />
<br />
Notice how the opposite of failure is "return".<br />
<br />
== Handling failures ==<br />
<br />
Each of the mentioned error handling mechanisms is equipped with a primitive for handling a failure.<br />
When dealing with a failure, it's obvious based on the type signature what might go wrong. In the example of head above, obviously head will fail if the list is empty.<br />
<br />
In any event, we need to instantiate MonadFailure in order to actually call the head function. The control-monad-failure package comes with instances for each of the mentioned error handling mechanisms.<br />
<br />
* Maybe. failure == Nothing<br />
* List. failure == []<br />
* IO. failure == throw<br />
* Either. failure == Left<br />
* ErrorT (provided by mtl or transformers). failure == throwError.<br />
<br />
However, there are also two other packages available which provide more resilient options.<br />
<br />
=== [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/control-monad-exception control-monad-exception ]===<br />
<br />
c-m-e provides a EM monad for explicitly typed, checked exceptions a la Java.<br />
The type of a EM computation carries the list of exceptions it can throw in its type. For example, let's say that we have a basic arithmetic expression evaluator which can throw divide by zero or sum overflow exceptions. Its type will be:<br />
<br />
eval :: (Throws DivByZero l, Throws SumOverflow l) => Expr -> EM l Double<br />
<br />
Correspondingly, a computation which calls eval and handles only the DivByZero exception gets the type:<br />
<br />
:t eval <expr> `catch` \DivByZero -> return 0<br />
eval <expr> :: Throws SumOverflow l => EM l Double<br />
<br />
<br />
=== [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/attempt attempt] ===<br />
<br />
Attempt is intended when you don't know what might go wrong, but you know it could happen. For example, let's say I want to define a type class:<br />
<br />
class Convert a b where<br />
convert :: a -> Attempt b<br />
<br />
Other libraries may want to instantiate Convert for their own types. However, when writing the Convert typeclass, I don't know exactly what failures may occur. When writing the "Convert String Int" instances, it might be InvalidInteger. But when writing the "Convert English Spanish" typeclass (hey, it could happen) it might be InvalidGrammar.<br />
<br />
= http://hackage.haskell.org/cgi-bin/hackage-scripts/package/safe-failure safe-failure] =<br />
<br />
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/safe-failure safe-failure] is a collection of functions from the Prelude which return values in the MonadFailure monad. It provides all the functions available in Neil Mitchell's safe package, plus a few extra.<br />
<br />
= Stack traces =<br />
<br />
As an added bonus, both control-monad-exception and attempt provide stack traces, or more exactly [http://pepeiborra.posterous.com/monadic-stack-traces-that-make-a-lot-of-sense monadic call traces], via [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/monadloc MonadLoc].<br />
<br />
= References =<br />
<br />
* http://www.randomhacks.net/articles/2007/03/10/haskell-8-ways-to-report-errors<br />
* http://www.haskell.org/pipermail/libraries/2007-March/007010.html</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Failure&diff=31470Failure2009-11-08T01:40:46Z<p>Mnislaih: </p>
<hr />
<div>This page discusses the not-yet-released control-monad-failure package and its associated packages. As of this writing (November 7, 2009), the packages are expected to be released within the next week.<br />
<br />
= Exceptions, errors, failures oh my! =<br />
<br />
Terminology is a little confusing. There's a few different things floating around:<br />
<br />
* Error usually refers to a programming error. It can also refer to the "error" function, which in fact causes a runtime exception to be triggered.<br />
* Exception usually refers to an exception which is thrown in the IO monad. It can also refer to the actually typeclass "Exception" which was introduced along with extensible exceptions.<br />
* Fail is referring to the "fail" function, which is part of the Monad typeclass and is almost universally despised.<br />
<br />
To avoid the baggage and name clashes introduced with all of the above, we use the term failure. This name is used consistently for module names, type classes, function names and the abstract concept.<br />
<br />
But what is a failure? It's any time that something does not succeed. Of course, this depends on your definition of success. Here are some examples:<br />
<br />
* readInt fails when it receives invalid input.<br />
* head fails when it receives an empty list.<br />
* lookup fails when the key is not find in the list.<br />
* at (also known as !!) fails when the index is past the end of the list.<br />
<br />
Now that we know what a failure is, let's discuss how to deal with it.<br />
<br />
= Prior Art =<br />
<br />
There are currently a number of methods available for dealing with failures. However, all of them are lacking in some way:<br />
<br />
* Maybe. However, there's no information on *what* failed.<br />
* The error function. But not all failures should be fatal.<br />
* IO exceptions. But they force your code into your IO monad, plus it's non-obvious that a function might fail with an exception based solely on its return type.<br />
* Custom error values. But how do you compose two libraries together?<br />
* The Either/ErrorT monads. Apart from the fact that Either is not a Monad by default (you can use the mtl or transformers instances, but that introduces undesirable orphan instances), the main problem with these lies in composability and extensibility.<br />
<br />
This abundance of error handling methods leads to lots of gluing code when combining libraries which use different notions of failure. <br />
Examples:<br />
<br />
* The partial functions in the Prelude and other base modules, such as head, tail, fromJust, lookup, etc. use the error function.<br />
* parsec models failure using Either ParseError<br />
* http models failure using Either ConnError<br />
* The HDBC package models failure using the SQLError exception<br />
* The cgi package uses exceptions<br />
<br />
Quoting from Eric Kidd:<br />
{| class="wikitable"<br />
|-<br />
|<br />
<pre><br />
Consider a program to download a web page and parse it:<br />
<br />
1. Network.URI.parseURI returns (Maybe URI).<br />
2. Network.HTTP.simpleHTTP returns (IO (Result Request)), which is basically a broken version of (IO (Either ConnError Request)).<br />
3. Parsec returns (Either ParseError a)<br />
<br />
So there's no hope that I can write anything like:<br />
<br />
do uri <- parseURI uriStr<br />
doc <- evenSimplerHTTP uri<br />
parsed <- parse grammar uriStr doc<br />
</pre><br />
|}<br />
<br />
= Enter control-monad-failure, stage left =<br />
<br />
What we want is an abstract notion of failure which does not tie us to any particular error handling mechanism. This is what the [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/control-monad-failure control-monad-failure] package intents to provide. <br />
<br />
MonadFailure is the typeclass used to model this abstract notion of failure. It lives in the Control.Monad.Failure module and consists entirely of the following two lines:<br />
<br />
class Monad m => MonadFailure e m where<br />
failure :: e -> m a<br />
<br />
So now, you could define a safe head function as follows:<br />
<br />
data EmptyListFailure = EmptyListFailure<br />
head :: MonadFailure EmptyListFailure m => [a] -> m a<br />
head [] = failure EmptyListFailure<br />
head (x:_) = return x<br />
<br />
Notice how the opposite of failure is "return".<br />
<br />
== Handling failures ==<br />
<br />
Each of the mentioned error handling mechanisms is equipped with a primitive for handling a failure.<br />
When dealing with a failure, it's obvious based on the type signature what might go wrong. In the example of head above, obviously head will fail if the list is empty.<br />
<br />
In any event, we need to instantiate MonadFailure in order to actually call the head function. The control-monad-failure package comes with instances for each of the mentioned error handling mechanisms.<br />
<br />
* Maybe. failure == Nothing<br />
* List. failure == []<br />
* IO. failure == throw<br />
* Either. failure == Left<br />
* ErrorT (provided by mtl or transformers). failure == throwError.<br />
<br />
However, there are also two other packages available which provide more resilient options.<br />
<br />
=== [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/control-monad-exception control-monad-exception ]===<br />
<br />
c-m-e provides a EM monad for explicitly typed, checked exceptions a la Java.<br />
The type of a EM computation carries the list of exceptions it can throw in its type. For example, let's say that we have a basic arithmetic expression evaluator which can throw divide by zero or sum overflow exceptions. Its type will be:<br />
<br />
eval :: (Throws DivByZero l, Throws SumOverflow l) => Expr -> EM l Double<br />
<br />
Correspondingly, a computation which calls eval and handles only the DivByZero exception gets the type:<br />
<br />
:t eval <expr> `catch` \DivByZero -> return 0<br />
eval <expr> :: Throws SumOverflow l => EM l Double<br />
<br />
<br />
=== [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/attempt attempt] ===<br />
<br />
Attempt is intended when you don't know what might go wrong, but you know it could happen. For example, let's say I want to define a type class:<br />
<br />
class Convert a b where<br />
convert :: a -> Attempt b<br />
<br />
Other libraries may want to instantiate Convert for their own types. However, when writing the Convert typeclass, I don't know exactly what failures may occur. When writing the "Convert String Int" instances, it might be InvalidInteger. But when writing the "Convert English Spanish" typeclass (hey, it could happen) it might be InvalidGrammar.<br />
<br />
= safe-failure =<br />
<br />
safe-failure is a collection of functions which return values in the MonadFailure monad. It provides all the functions available in Neil Mitchell's safe package, plus a few extra.<br />
<br />
= Stack traces =<br />
<br />
As an added bonus, both control-monad-exception and attempt provide stack traces, or more exactly [http://pepeiborra.posterous.com/monadic-stack-traces-that-make-a-lot-of-sense monadic call traces], via [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/monadloc MonadLoc].<br />
<br />
= References =<br />
<br />
* http://www.randomhacks.net/articles/2007/03/10/haskell-8-ways-to-report-errors<br />
* http://www.haskell.org/pipermail/libraries/2007-March/007010.html</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Failure&diff=31469Failure2009-11-08T01:37:17Z<p>Mnislaih: </p>
<hr />
<div>This page discusses the not-yet-released control-monad-failure package and its associated packages. As of this writing (November 7, 2009), the packages are expected to be released within the next week.<br />
<br />
= Exceptions, errors, failures oh my! =<br />
<br />
Terminology is a little confusing. There's a few different things floating around:<br />
<br />
* Error usually refers to a programming error. It can also refer to the "error" function, which in fact causes a runtime exception to be triggered.<br />
* Exception usually refers to an exception which is thrown in the IO monad. It can also refer to the actually typeclass "Exception" which was introduced along with extensible exceptions.<br />
* Fail is referring to the "fail" function, which is part of the Monad typeclass and is almost universally despised.<br />
<br />
To avoid the baggage and name clashes introduced with all of the above, we use the term failure. This name is used consistently for module names, type classes, function names and the abstract concept.<br />
<br />
But what is a failure? It's any time that something does not succeed. Of course, this depends on your definition of success. Here are some examples:<br />
<br />
* readInt fails when it receives invalid input.<br />
* head fails when it receives an empty list.<br />
* lookup fails when the key is not find in the list.<br />
* at (also known as !!) fails when the index is past the end of the list.<br />
<br />
Now that we know what a failure is, let's discuss how to deal with it.<br />
<br />
= Prior Art =<br />
<br />
There are currently a number of methods available for dealing with failures. However, all of them are lacking in some way:<br />
<br />
* Maybe. However, there's no information on *what* failed.<br />
* The error function. But not all failures should be fatal.<br />
* IO exceptions. But they force your code into your IO monad, plus it's non-obvious that a function might fail with an exception based solely on its return type.<br />
* Custom error values. But how do you compose two libraries together?<br />
* The Either/ErrorT monads. Apart from the fact that Either is not a Monad by default (you can use the mtl or transformers instances, but that introduces undesirable orphan instances), the main problem with these lies in composability and extensibility.<br />
<br />
This abundance of error handling methods leads to lots of gluing code when combining libraries which use different notions of failure. <br />
Examples:<br />
<br />
* The partial functions in the Prelude and other base modules, such as head, tail, fromJust, lookup, etc. use the error function.<br />
* parsec models failure using Either ParseError<br />
* http models failure using Either ConnError<br />
* The HDBC package models failure using the SQLError exception<br />
* The cgi package uses exceptions<br />
<br />
Quoting from Eric Kidd:<br />
{| class="wikitable"<br />
|-<br />
|<br />
<pre><br />
Consider a program to download a web page and parse it:<br />
<br />
1. Network.URI.parseURI returns (Maybe URI).<br />
2. Network.HTTP.simpleHTTP returns (IO (Result Request)), which is basically a broken version of (IO (Either ConnError Request)).<br />
3. Parsec returns (Either ParseError a)<br />
<br />
So there's no hope that I can write anything like:<br />
<br />
do uri <- parseURI uriStr<br />
doc <- evenSimplerHTTP uri<br />
parsed <- parse grammar uriStr doc<br />
</pre><br />
|}<br />
<br />
= Enter control-monad-failure, stage left =<br />
<br />
What we want is an abstract notion of failure which does not tie us to any particular error handling mechanism. This is what the [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/control-monad-failure control-monad-failure] package intents to provide. <br />
<br />
MonadFailure is the typeclass used to model this abstract notion of failure. It lives in the Control.Monad.Failure module and consists entirely of the following two lines:<br />
<br />
class Monad m => MonadFailure e m where<br />
failure :: e -> m a<br />
<br />
So now, you could define a safe head function as follows:<br />
<br />
data EmptyListFailure = EmptyListFailure<br />
head :: MonadFailure EmptyListFailure m => [a] -> m a<br />
head [] = failure EmptyListFailure<br />
head (x:_) = return x<br />
<br />
Notice how the opposite of failure is "return".<br />
<br />
== Handling failures ==<br />
<br />
Each of the mentioned error handling mechanisms is equipped with a primitive for handling a failure.<br />
When dealing with a failure, it's obvious based on the type signature what might go wrong. In the example of head above, obviously head will fail if the list is empty.<br />
<br />
In any event, we need to instantiate MonadFailure in order to actually call the head function. The control-monad-failure package comes with instances for each of the mentioned error handling mechanisms.<br />
<br />
* Maybe. failure == Nothing<br />
* List. failure == []<br />
* IO. failure == throw<br />
* Either. failure == Left<br />
* ErrorT (provided by mtl or transformers). failure == throwError.<br />
<br />
However, there are also two other packages available which provide more resilient options.<br />
<br />
=== [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/control-monad-exception control-monad-exception ]===<br />
<br />
c-m-e provides a EM monad for explicitly typed, checked exceptions a la Java.<br />
The type of a EM computation carries the list of exceptions it can throw in its type. For example, let's say that we have a basic arithmetic expression evaluator which can throw divide by zero or sum overflow exceptions. Its type will be:<br />
<br />
eval :: (Throws DivByZero l, Throws SumOverflow l) => Expr -> EM l Double<br />
<br />
Correspondingly, a computation which calls eval and handles only the DivByZero exception gets the type:<br />
<br />
:t eval <expr> `catch` \DivByZero -> return 0<br />
eval <expr> :: Throws SumOverflow l => EM l Double<br />
<br />
<br />
=== [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/attempt attempt] ===<br />
<br />
Attempt is intended when you don't know what might go wrong, but you know it could happen. For example, let's say I want to define a type class:<br />
<br />
class Convert a b where<br />
convert :: a -> Attempt b<br />
<br />
Other libraries may want to instantiate Convert for their own types. However, when writing the Convert typeclass, I don't know exactly what failures may occur. When writing the "Convert String Int" instances, it might be InvalidInteger. But when writing the "Convert English Spanish" typeclass (hey, it could happen) it might be InvalidGrammar.<br />
<br />
= safe-failure =<br />
<br />
safe-failure is a collection of functions which return values in the MonadFailure monad. It provides all the functions available in Neil Mitchell's safe package, plus a few extra.<br />
<br />
= Stack traces =<br />
<br />
As an added bonus, both control-monad-exception and attempt support MonadLoc, meaning you can get stack traces. More information available in Jose's blog post [http://pepeiborra.posterous.com/monadic-stack-traces-that-make-a-lot-of-sense].<br />
<br />
= References =<br />
<br />
* http://www.randomhacks.net/articles/2007/03/10/haskell-8-ways-to-report-errors<br />
* http://www.haskell.org/pipermail/libraries/2007-March/007010.html</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Failure&diff=31468Failure2009-11-08T00:43:44Z<p>Mnislaih: </p>
<hr />
<div>This page discusses the not-yet-released control-monad-failure package and its associated packages. As of this writing (November 7, 2009), the packages are expected to be released within the next week.<br />
<br />
= Exceptions, errors, failures oh my! =<br />
<br />
Terminology is a little confusing. There's a few different things floating around:<br />
<br />
* Error usually refers to a programming error. It can also refer to the "error" function, which in fact causes a runtime exception to be triggered.<br />
* Exception usually refers to an exception which is thrown in the IO monad. It can also refer to the actually typeclass "Exception" which was introduced along with extensible exceptions.<br />
* Fail is referring to the "fail" function, which is part of the Monad typeclass and is almost universally despised.<br />
<br />
To avoid the baggage and name clashes introduced with all of the above, we use the term failure. This name is used consistently for module names, type classes, function names and the abstract concept.<br />
<br />
But what is a failure? It's any time that something does not succeed. Of course, this depends on your definition of success. Here are some examples:<br />
<br />
* readInt fails when it receives invalid input.<br />
* head fails when it receives an empty list.<br />
* lookup fails when the key is not find in the list.<br />
* at (also known as !!) fails when the index is past the end of the list.<br />
<br />
Now that we know what a failure is, let's discuss how to deal with it.<br />
<br />
= Prior Art =<br />
<br />
There are currently a number of methods available for dealing with failures. However, all of them are lacking in some way:<br />
<br />
* Maybe. However, there's no information on *what* failed.<br />
* Either String. Two problems here: 1) Either is not a Monad by default. You can use the mtl or transformers instances, but that introduces orphan instances and all the associated issues. 2) A String is a bit limiting sometimes.<br />
* The error function. But not all failures should be fatal.<br />
* Runtime exceptions. You need to be in IO to handle it, plus it's non-obvious that an exception might have been thrown based on return type.<br />
* Custom error values. But how do you compose two libraries together?<br />
<br />
= Enter control-monad-failure, stage left =<br />
<br />
What we want is a mechanism for failure which is flexible enough to provide all the information we might want. That happens to be provided very nicely by extensible exceptions. control-monad-failure is simply a mechanism for using extensible exceptions outside of the IO monad while explicitly stating the possibility of failure.<br />
<br />
MonadFailure is the typeclass used to glue everything else together. It lives in the Control.Monad.Failure module in the control-monad-failure package (fancy that), and consists entirely of the following two lines:<br />
<br />
class Monad m => MonadFailure e m where<br />
failure :: e -> m a<br />
<br />
So now, you could define a safe head function as follows:<br />
<br />
data EmptyListFailure = EmptyListFailure<br />
head :: MonadFailure EmptyListFailure m => [a] -> m a<br />
head [] = failure EmptyListFailure<br />
head (x:_) = return x<br />
<br />
Notice how the opposite of failure is "return".<br />
<br />
== Catching failures ==<br />
<br />
Catching isn't really the right term at all. When you catch an exception in the IO monad, it's sort of like fishing in the dark abyss which is the impurity of the real world. When dealing with a failure, it's obvious based on the type signature what might go wrong. In the example of head above, obviously head won't succeed if the list is empty.<br />
<br />
In any event, we need some instances of MonadFailure in order to actually call the head function. There are some built in with the control-monad-failure package. However, there are also two other packages available which provide more resilient options. The built in offerings are:<br />
<br />
* Maybe. failure == Nothing<br />
* List. failure == []<br />
* IO. failure == throw<br />
* Either. failure == Left<br />
* ErrorT (provided by mtl or transformers). failure == throwError.<br />
<br />
However, each of these runs into the issues described previously.<br />
<br />
=== control-monad-exception ===<br />
<br />
c-m-e provides a EM monad for explicitly typed, checked exceptions a la Java.<br />
The type of a EM computation carries the list of exceptions it can throw in its type. For example, let's say that we have a basic arithmetic expression evaluator which can throw divide by zero or sum overflow exceptions. Its type will be:<br />
<br />
eval :: (Throws DivByZero l, Throws SumOverflow l) => Expr -> EM l Double<br />
<br />
Correspondingly, a computation which calls eval and handles only the DivByZero exception gets the type:<br />
<br />
:t eval <expr> `catch` \DivByZero -> return 0<br />
eval <expr> :: Throws SumOverflow l => EM l Double<br />
<br />
<br />
=== attempt ===<br />
<br />
Attempt is intended when you don't know what might go wrong, but you know it could happen. For example, let's say I want to define a type class:<br />
<br />
class Convert a b where<br />
convert :: a -> Attempt b<br />
<br />
Other libraries may want to instantiate Convert for their own types. However, when writing the Convert typeclass, I don't know exactly what failures may occur. When writing the "Convert String Int" instances, it might be InvalidInteger. But when writing the "Convert English Spanish" typeclass (hey, it could happen) it might be InvalidGrammar.<br />
<br />
= safe-failure =<br />
<br />
safe-failure is a collection of functions which return values in the MonadFailure monad. It provides all the functions available in Neil Mitchell's safe package, plus a few extra.<br />
<br />
= Stack traces =<br />
<br />
As an added bonus, both control-monad-exception and attempt support MonadLoc, meaning you can get stack traces. More information available in Jose's blog post [http://pepeiborra.posterous.com/monadic-stack-traces-that-make-a-lot-of-sense].</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Google_Code_Jam/Text_Messaging_Outrage&diff=24809Google Code Jam/Text Messaging Outrage2008-12-15T14:45:16Z<p>Mnislaih: </p>
<hr />
<div>== Solution ==<br />
<haskell><br />
<br />
main = (enumFromTo (1::Int) <$> readLn) >>= mapM_ go<br />
where go i = do<br />
[p,k,l] <- map read . words <$> getLine<br />
nn <- map read . words <$> getLine<br />
printf "Case #%i: %i\n" i (solve k nn)<br />
<br />
solve :: Int -> [Integer] -> Integer<br />
solve k l = let rounds = map sum $ chunks k $ sortBy (flip compare) l<br />
in sum $ zipWith (*) [1..] rounds<br />
chunks n [] = []<br />
chunks n as = bs : chunks n cs where (bs,cs) = splitAt n as<br />
<br />
</haskell></div>Mnislaihhttps://wiki.haskell.org/index.php?title=Google_Code_Jam/Mousetrap&diff=24807Google Code Jam/Mousetrap2008-12-15T14:34:09Z<p>Mnislaih: </p>
<hr />
<div>== Problem ==<br />
<br />
Mousetrap is a simple card game for one player. It is played with a shuffled deck of cards numbered 1 through K, face down. You play by revealing the top card of the deck and then putting it on the bottom of the deck, keeping count of how many cards you have revealed. If you reveal a card whose number matches the current count, remove it from the deck and reset the count. If the count ever reaches K+1, you have lost. If the deck runs out of cards, you win.<br />
<br />
Suppose you have a deck of 5 cards, in the order 2, 5, 3, 1, 4. You will reveal the 2 on count 1, the 5 on count 2, then the 3 on count 3. Since the value matches the count, you remove the 3 from the deck, and reset the count. You now have 4 cards left in the order 1, 4, 2, 5. You then reveal the 1 on count 1, and remove it as well (you're doing great so far!). Continuing in this way you will remove the 2, then the 4, and then finally the 5 for victory.<br />
<br />
You would like to set up a deck of cards in such a way that you will win the game and remove the cards in increasing order. We'll call a deck organized in this way "perfect." For example, with 4 cards you can organize the deck as 1, 4, 2, 3, and you will win by removing the cards in the order 1, 2, 3, 4.<br />
<br />
=== Input ===<br />
<br />
The first line of input gives the number of cases, T. Each test case starts with a line containing K, the number of cards in a deck. The next line starts with an integer n, which is followed by n integers (d1,d2, ...), indices into the deck.<br />
<br />
=== Output ===<br />
<br />
For each test case, output one line containing "Case #x: " followed by n integers (k1,k2, ...), where ki is the value of the card at index di of a perfect deck of size K. The numbers in the output should be separated by spaces, and there must be at least one space following the colon in each "Case #x:" line.<br />
<br />
=== Limits===<br />
<br />
==== Small dataset ====<br />
<br />
T = 100, 1 ≤ K ≤ 5000, 1 ≤ n ≤ 100, 1 ≤ di ≤ K.<br />
<br />
==== Large dataset ====<br />
<br />
T = 10, 1 ≤ K ≤ 1000000, 1 ≤ n ≤ 100, 1 ≤ di ≤ K.<br />
<br />
=== Sample ===<br />
<br />
==== Input ====<br />
2<br />
5<br />
5 1 2 3 4 5<br />
15<br />
4 3 4 7 10<br />
==== Output ====<br />
Case #1: 1 3 2 5 4<br />
Case #2: 2 8 13 4<br />
<br />
== Solutions ==<br />
==== Naive solution ====<br />
This solution is not fast enough for the large dataset, but suffices widely for the small one.<br />
<br />
<haskell><br />
{-# LANGUAGE ViewPatterns, PatternGuards #-}<br />
<br />
import qualified Data.Sequence as S<br />
import Data.Sequence ((|>), (<|), (><), ViewL(..))<br />
import Text.Printf<br />
<br />
main = (enumFromTo (1::Int) <$> readLn) >>= mapM_ go<br />
where go i = do<br />
k <- read <$> getLine<br />
(_:ii) <- (map read . words) <$> getLine<br />
printf "Case #%i: %s\n" i (solve k ii)<br />
<br />
solve p ii = (unwords . map show . getIndexes ii . maindeck) p<br />
<br />
type Deck = (S.Seq Int, Cursor)<br />
type Cursor = Int<br />
<br />
card <> (cards,cursor) = pre >< (card <| post)<br />
where (pre, post) = S.splitAt cursor cards<br />
n = S.length cards<br />
<br />
maindeck n = deck n n<br />
<br />
deck 2 n | odd (n-1) = (S.fromList [n-1, n],0)<br />
| otherwise = (S.fromList [n,n-1],0)<br />
deck n' n | n' == n = (1 <| flipDeck (deck (n-1) n), 0)<br />
deck i n = (card <> deck', newcursor)<br />
where card = (n - i + 1)<br />
deck'@(_, cursor) = deck (i-1) n<br />
newcursor = (cursor + i - ((card - 1) `mod` i)) `mod` i<br />
<br />
flipDeck (cards, i) = post >< pre where (pre, post) = S.splitAt i cards<br />
<br />
getIndexes ii (seq, pointer) = map (\i -> S.index seq ((i + pointer - 1) `mod` S.length seq )) ii<br />
<br />
</haskell><br />
<br />
=== The beef ===<br />
This solution is derived from the previous one by removing all the intermediate Sequences. Cryptic, but good enough for the large dataset. <br />
<br />
<haskell><br />
{-# LANGUAGE PatternGuards #-}<br />
<br />
import Control.Applicative<br />
import Text.Printf<br />
<br />
main = (enumFromTo (1::Int) <$> readLn) >>= mapM_ go<br />
where go i = do<br />
k <- read <$> getLine<br />
(_:ii) <- (map read . words) <$> getLine<br />
printf "Case #%i: %s\n" i (solve k ii)<br />
<br />
solve k = unwords . map (show . deck k k) . map pred<br />
<br />
-- Deck is the type of functions that given an index, tell you the card placed<br />
-- in that index in a perfect mousetrap card configuration<br />
type Deck = Index -> Card<br />
type Index = Int<br />
type Card = Int<br />
<br />
----------------------<br />
-- Working with cards<br />
<br />
maindeck k = deck k k<br />
<br />
deck n 2 0 | odd (n-1) = n - 1<br />
| otherwise = n<br />
deck n 2 1 | odd (n-1) = n<br />
| otherwise = n - 1<br />
deck n 1 0 = n<br />
deck n n' 0 | n' == n = 1<br />
deck n n' i | n' == n = deck n (n-1) (i - 1)<br />
deck n m i | i == card_in = card<br />
| otherwise = deck n (m-1) (i' - 1)<br />
where card = (n - m + 1)<br />
card_in = rotate (card - 1)<br />
i' = rotate (i - card_in)<br />
rotate = rotateN m<br />
<br />
rotateN n i | i < 0 = rotateN n (n + i)<br />
| otherwise = i `mod` n<br />
</haskell></div>Mnislaihhttps://wiki.haskell.org/index.php?title=Google_Code_Jam/Mousetrap&diff=24806Google Code Jam/Mousetrap2008-12-15T14:28:56Z<p>Mnislaih: </p>
<hr />
<div>== Problem ==<br />
<br />
Mousetrap is a simple card game for one player. It is played with a shuffled deck of cards numbered 1 through K, face down. You play by revealing the top card of the deck and then putting it on the bottom of the deck, keeping count of how many cards you have revealed. If you reveal a card whose number matches the current count, remove it from the deck and reset the count. If the count ever reaches K+1, you have lost. If the deck runs out of cards, you win.<br />
<br />
Suppose you have a deck of 5 cards, in the order 2, 5, 3, 1, 4. You will reveal the 2 on count 1, the 5 on count 2, then the 3 on count 3. Since the value matches the count, you remove the 3 from the deck, and reset the count. You now have 4 cards left in the order 1, 4, 2, 5. You then reveal the 1 on count 1, and remove it as well (you're doing great so far!). Continuing in this way you will remove the 2, then the 4, and then finally the 5 for victory.<br />
<br />
You would like to set up a deck of cards in such a way that you will win the game and remove the cards in increasing order. We'll call a deck organized in this way "perfect." For example, with 4 cards you can organize the deck as 1, 4, 2, 3, and you will win by removing the cards in the order 1, 2, 3, 4.<br />
<br />
=== Input ===<br />
<br />
The first line of input gives the number of cases, T. Each test case starts with a line containing K, the number of cards in a deck. The next line starts with an integer n, which is followed by n integers (d1,d2, ...), indices into the deck.<br />
<br />
=== Output ===<br />
<br />
For each test case, output one line containing "Case #x: " followed by n integers (k1,k2, ...), where ki is the value of the card at index di of a perfect deck of size K. The numbers in the output should be separated by spaces, and there must be at least one space following the colon in each "Case #x:" line.<br />
<br />
=== Limits===<br />
<br />
==== Small dataset ====<br />
<br />
T = 100, 1 ≤ K ≤ 5000, 1 ≤ n ≤ 100, 1 ≤ di ≤ K.<br />
<br />
==== Large dataset ====<br />
<br />
T = 10, 1 ≤ K ≤ 1000000, 1 ≤ n ≤ 100, 1 ≤ di ≤ K.<br />
<br />
=== Sample ===<br />
<br />
==== Input ====<br />
2<br />
5<br />
5 1 2 3 4 5<br />
15<br />
4 3 4 7 10<br />
==== Output ====<br />
Case #1: 1 3 2 5 4<br />
Case #2: 2 8 13 4<br />
<br />
== Solutions ==<br />
==== Naive solution ====<br />
<haskell><br />
This solution is not fast enough for the large dataset, but suffices widely for the small one.<br />
{{{<br />
{-# LANGUAGE ViewPatterns, PatternGuards #-}<br />
<br />
import qualified Data.Sequence as S<br />
import Data.Sequence ((|>), (<|), (><), ViewL(..))<br />
import Text.Printf<br />
<br />
main = (enumFromTo (1::Int) <$> readLn) >>= mapM_ go<br />
where go i = do<br />
k <- read <$> getLine<br />
(_:ii) <- (map read . words) <$> getLine<br />
printf "Case #%i: %s\n" i (solve k ii)<br />
<br />
solve p ii = (unwords . map show . getIndexes ii . maindeck) p<br />
<br />
type Deck = (S.Seq Int, Cursor)<br />
type Cursor = Int<br />
<br />
card <> (cards,cursor) = pre >< (card <| post)<br />
where (pre, post) = S.splitAt cursor cards<br />
n = S.length cards<br />
<br />
maindeck n = deck n n<br />
<br />
deck 2 n | odd (n-1) = (S.fromList [n-1, n],0)<br />
| otherwise = (S.fromList [n,n-1],0)<br />
deck n' n | n' == n = (1 <| flipDeck (deck (n-1) n), 0)<br />
deck i n = (card <> deck', newcursor)<br />
where card = (n - i + 1)<br />
deck'@(_, cursor) = deck (i-1) n<br />
newcursor = (cursor + i - ((card - 1) `mod` i)) `mod` i<br />
<br />
flipDeck (cards, i) = post >< pre where (pre, post) = S.splitAt i cards<br />
<br />
getIndexes ii (seq, pointer) = map (\i -> S.index seq ((i + pointer - 1) `mod` S.length seq )) ii<br />
<br />
</haskell></div>Mnislaihhttps://wiki.haskell.org/index.php?title=Hac_2007_II/Projects&diff=16089Hac 2007 II/Projects2007-10-06T15:22:24Z<p>Mnislaih: </p>
<hr />
<div>= Generic Information =<br />
<br />
You can apply for an account and a project using<br />
[http://community.haskell.org/admin/ the community server]. Ping Igloo on #haskell-hac07 and he'll create the account. You can also apply for a project.<br />
<br />
Once you have an account and a project, you upload a Darcs repository as follows. First, initialize your repository on the server:<br />
<br />
$ ssh community.haskell.org<br />
you@haskell:~$ cd /srv/code/yourproject<br />
you@haskell:/srv/code/yourproject$ darcs init<br />
<br />
Then, log out and push your repository:<br />
<br />
$ darcs push community.haskell.org:/srv/code/yourproject<br />
<br />
= Who knows about what =<br />
<br />
A list of projects you've worked on or know fairly well:<br />
<br />
{| class="wikitable"<br />
! Name<br />
! Projects<br />
|-<br />
| dons<br />
| ByteString, xmonad, Data.Binary, lambdabot, hmp3, curses, QuickCheck, HPC, hs-plugins, yi, nobench/nofib, ghc<br />
|-<br />
| Binkley<br />
| ghc, darcs (a little bit)<br />
|-<br />
| skogsbaer (Stefan Wehr)<br />
| hscurses, rhaskell<br />
|-<br />
| Pepe<br />
| ghc (front end mostly), ghci debugger, cabal-install (very little)<br />
|-<br />
| ivant<br />
| Functional MetaPost, xmonad<br />
|-<br />
| kolmodin (Lennart Kolmodin)<br />
| Data.Binary, Gentoo Linux, Haste (Haskell Turbo-Edit,a Haskell IDE in Haskell), hackport (hackage for Gentoo), hinotify, dbus-haskell <br />
|-<br />
| Heffalump (Ganesh Sittampalam)<br />
| darcs patch theory<br />
|-<br />
| [[User:Beschmi|beschmi]] (Benedikt Schmidt)<br />
| shim (emacs+ghc-api), darcs, xmonad<br />
|-<br />
| [[User:Conal|conal]] (Conal Elliott)<br />
| functional reactive programming, [[DataDriven]] evaluation, tangible functional programming, graphics, embedded compilers, applicative functors, wxHaskell<br />
|}<br />
<br />
= Active Projects =<br />
Please feel free to describe your current project here!<br />
<br />
== Cabal ==<br />
<br />
== ByteString network ==<br />
<br />
Change Network.* to use strict ByteStrings instead of Strings. It would also be nice to tidy up the #ifdef mess.<br />
<br />
Things to work on:<br />
<br />
# Add HUnit tests.<br />
# Write an echo server example.<br />
<br />
Done:<br />
<br />
# [http://code.haskell.org/network-bytestring/ Darcs repository] -- Hackage ready version of the send and receive functions (Network.Socket.ByteString).<br />
# Haddock documentation (could need some polish).<br />
<br />
Current hacker(s): tibbe (Johan Tibell)<br />
<br />
== Data.Binary ==<br />
<br />
updating to 6.8, adding smp parallel testsuite driver.<br />
<br />
Current hackers: dons<br />
<br />
== xmonad ==<br />
<br />
Testing, HPC coverage, code polishing., new layouts, notification support, scratchpad (a la ion)<br />
<br />
Current hackers: dons, ganesh, conrad, nomeata, tibbe, beschmi<br />
<br />
== Probability monads ==<br />
<br />
A really cool existing implementation: [http://web.engr.oregonstate.edu/~erwig/pfp/ Probabilistic functional programming]<br />
<br />
[http://www.randomhacks.net/articles/2007/10/02/probability-monads-at-hac-07-ii Darcs repository and draft paper].<br />
<br />
Things to work on:<br />
<br />
# Get MaybeT into Hackage.<br />
# Is WriterT really the right monad transformer? We want the join and bind operations, but not the rest of the MonadWriter type class.<br />
# Should probabilities be represented as floats, fractions or a type class?<br />
# Can this run fast enough to be useful?<br />
<br />
Done:<br />
<br />
# [http://www.randomhacks.net/tmp/MaybeT/Control-Monad-Maybe.html MaybeT docs] and [http://code.haskell.org/maybet/ Darcs repository]. This should have all the features of [[New_monads/MaybeT]], except for the potentially ambiguous MonadPlus instance.<br />
# [http://code.haskell.org/monadrandom/ MonadRandom] is now documented and packaged.<br />
# The [http://www.randomhacks.net/darcs/probability/ Probability] library:<br />
#* Now builds using external MaybeT and MonadRandom.<br />
#* Added support for representing probabilities as doubles and floats.<br />
#* Merged Dist instances and helper code for Rand, BRand, DDist, and BDDist from example code and paper.<br />
<br />
Current hacker(s): ekidd (Eric Kidd)<br />
<br />
== Yi hacking ==<br />
<br />
Yi needs a lot of love and doesn't work out of the box for me. One of the nice thing to try to do is to add the collaborative editing plugin to yi (in the spirit of the [http://gobby.0x539.de/trac/ Gobby editor]).<br />
* vincenz: Definitely would like to add some usability input here regarding Gobby functionality (having used it and having found it lacking in several areas, areas that could be improved through reusing some darcs theory).<br />
* ivant: also need to add unicode support to yi<br />
* vincenz: Move away from System.Filepath to something std supported<br />
* Cabalize the current 'Setup.hs' *Cabal hackers welcome for help*<br />
* Update the regex dependencies to work with the newest one.<br />
* Work splatch into Yi<br />
<br />
Current hacker(s): ivant (Ivan Tarasov), vincenz (Christophe Poucet)<br />
<br />
== Splatch ==<br />
Patching of splices, or otherwise said, a patch-model for working concurrently on one piece of text.<br />
<br />
Current hacker(s): ivant (Ivan Tarasov), vincenz (Christophe Poucet)<br />
<br />
== Shim ==<br />
<br />
Port shim to GHC 6.8<br />
<br />
Current hacker(s): beschmi (Benedikt Schmidt)<br />
<br />
== Tangible functional programming ==<br />
<br />
Some to-do items:<br />
* More built-ins<br />
* Save<br />
* Improved user experience for gestural composition, e.g., drag & drop<br />
* Does it work on MacOS? Linux?<br />
* Sum types<br />
* Code generation via hs-plugins or ghc-api or Harpy.<br />
<br />
Current hacker(s): [[User:Conal|conal]]<br />
<br />
== General composition tools ==<br />
<br />
=== Type composition & related ===<br />
<br />
[[TypeCompose]]: some classes & instances for forms of type composition (including contravariant functors and applicative functors)<br />
<br />
Current hacker(s): [[User:Conal|conal]]<br />
<br />
=== Deep arrows ===<br />
<br />
[[DeepArrow]]: a framework for composable "editors" of pure values<br />
<br />
Current hacker(s): [[User:Conal|conal]]<br />
<br />
== Source browsing ==<br />
<br />
[http://tiddlywiki.com TiddlyWiki]-based code & documentation browser. Syntax-colored and all identifiers fully hyperlinked to sources. Thanks to TiddlyWiki, the browsing experience is fluid & self-organizing.<br />
<br />
Bring together disparate functionality from HsColour & Haddock, and add auto-generated hyperlinking. Apply to all the code on Hackage.<br />
<br />
Current hacker(s): [[User:Conal|conal]]<br />
<br />
== Graphics ==<br />
<br />
Fast general, pure-Haskell image synthesis (speed of [http://conal.net/Pan Pan] or [http://conal.net/Pajama Pajama] but via ghc). Use Harpy or a new hs-plugins.<br />
<br />
Current hacker(s): [[User:Conal|conal]]<br />
<br />
== General dependency tracking & updating ==<br />
<br />
Simple, general dependency tracking & execution formulated as an [[applicative functor]] and using [[DataDriven]] computation. Applies uniformly to recompiling, re-executing, installing, compiler-recompiling, GUI specification and execution, etc. For compilation, it can give more precise (efficient) recompilation than language-specific tools (e.g., <code>hmake</code> and <code>ghc --make</code>) without being language-specific. Yields a continuous build system for free. No "make" info required (since inferred by construction). (Nontrivial language changes/improvements may be necessary.)<br />
<br />
Current hacker(s): [[User:Conal|conal]]<br />
<br />
== Backtraces in the GHCi debugger ==<br />
<br />
This has turned out to be really complicated, so look at [http://hackage.haskell.org/trac/ghc/wiki/LightweightCCSCallStack here] for the details. Sadly, Alexey stays only for the first day.<br />
<br />
Current hackers: pepe, Alexey<br />
<br />
== Coverage recording in the GHC testsuite ==<br />
<br />
We would like HPC coverage recording to be performed as a possible part of running the tests in the GHC testsuite. Code targeted by this could be the compiler code itself, the runtime system, the library code of a tested library, and the test code.<br />
<br />
Current hackers: thorkilnaur<br />
<br />
== Shim ==<br />
<br />
We still believe that Shim has a great potential to become an awesome IDE, and so we've decided to make it compatible with ghc 6.8<br />
<br />
Current hackers: beschmi, pepe</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Hac_2007_II&diff=16060Hac 2007 II2007-10-06T10:52:05Z<p>Mnislaih: </p>
<hr />
<div>[[Image:Freiburg-lambda.png|Hac 07 II|center]]<br />
<br />
[[Image:Hac-axe-icon.png|Hac icon]]<br />
<br />
'''Hac 07 II: Haskell Hackathon'''<br />
<br />
'''October 5-7, 2007'''<br />
<br />
'''University of Freiburg, Freiburg, Germany'''<br />
<br />
<br />
* [[/Register|Register for the Hackathon]]<br />
<br />
* [[/Attendees|Attendees organising page]]<br />
<br />
* [[/Projects|What we're working on]]<br />
<br />
== Photos / blogs ==<br />
<br />
* [http://stockwits.com/Hackathon.jpg Group Picture]<br />
* [http://lafalafu.com/krc/Images/hacday1/ A few from Tim, day 1]<br />
* [http://cgi.cse.unsw.edu.au/~dons/blog/2007/10/06#hac07-2-day1 Don's blog, day 1]<br />
* [http://www.joachim-breitner.de/blog/archives/269-Haskell-Hackathon-Hackage-vs.-Debian.html Joachim's blog, day 1]<br />
* [http://flickr.com/photos/nominolo/tags/hac2007ii/ nominolo's pictures], on Flickr<br />
* [http://flickr.com/photos/pepeiborra/tags/hac2007ii/ mnislaih's pictures], on Flickr<br />
== About ==<br />
<br />
The 3rd Haskell Hackathon will be held over 3 days, October 5-7 2007,<br />
at the University of Freiburg, in conjunction with the<br />
[http://www.cse.unsw.edu.au/~keller/haskellws/HaskellWorkshop.html Haskell Workshop] and<br />
[http://www.informatik.uni-bonn.de/~ralf/icfp07.html ICFP] 2007.<br />
It is a coding festival, focusing on producing and improving<br />
Haskell libraries, tools and infrastructure.<br />
<br />
To attend please [[/Register|register]], and get ready to hack!<br />
<br />
''Note: that it is not necessary to register for ICFP, or any of the associated conferences, if you only want to go to the Hackathon. The Hackathon itself will be '''free''', but you will have to pay for travel, accommodation and food.''<br />
<br />
== Registration ==<br />
<br />
If you will be attending add your name to the [[/Register|Registration page]].<br />
Numbers may be limited, depending on availablity of space.<br />
<br />
== Where ==<br />
<br />
The Hackathon will take place at the same venue as the IFL workshop, at<br />
[http://maps.google.com/maps/ms?ie=UTF8&hl=en&msa=0&om=1&msid=112565914073914710272.0000011293bc4c0bc450c&ll=47.999169,7.86046&spn=0.041064,0.078621&z=14 the Faculty of Applied Sciences] of the University of Freiburg. '''The room is 02-016 in building 101'''.<br />
<br />
You can reach the hackathon venue from the main train station by taking the "Breisgau S-Bahn" from "Freiburg - Hbf." to "FR Messe/Universitt". [http://proglang.informatik.uni-freiburg.de/IFL2007/timetable.pdf Here is a timetable] (pdf). Please note that most but not all trains stop at the hackathon venue. Also, some trains only run Monday to Friday ("Montag - Freitag") or on Saturday ("Samstag").<br />
<br />
Alternatively, you can walk from the city center to the hackathon (20 - 30 minutes). [http://maps.google.com/maps/ms?ie=UTF8&hl=en&msa=0&om=1&msid=112565914073914710272.0000011293bc4c0bc450c&ll=47.999169,7.86046&spn=0.041064,0.078621&z=14 The map] shows the exact route. <br />
[[Image:logo-klein-07-2.png|frame|]]<br />
<br />
The Hackathon will be integrated with the university [http://sommercampus2007.informatik.uni-freiburg.de/WikiAbstract summer campus]. This will give us all the infrastructure (room, Internet, etc) at minimal hassle. '''Note:''' There won't be any stationary PCs, so you should bring a laptop with you.<br />
<br />
=== Local information ===<br />
<br />
For local information (travel, accommodation etc) see the<br />
[http://proglang.informatik.uni-freiburg.de/ICFP2007/ ICFP local info page].<br />
<br />
[http://proglang.informatik.uni-freiburg.de/IFL2007/travel-information.shtml Travel information page]<br />
<br />
Airport maps:<br />
* [http://maps.google.com/maps/ms?ie=UTF8&hl=en&msa=0&ll=48.705463,9.876709&spn=4.945094,10.063477&z=7&om=1&msid=112565914073914710272.000001129e6f892b7a21e Airports]<br />
<br />
== Dates ==<br />
<br />
Hac 2007 II will take place on Fri 5 Oct to Sun 7 Oct. The following<br />
table shows the workshops and conferences held in Freiburg during the<br />
ICFP period:<br />
<br />
{| class="wikitable"<br />
|-<br />
|Date || Events<br />
|-<br />
|Thu 27 Sep || IFL<br />
|-<br />
|Fri 28 Sep || IFL<br />
|-<br />
|Sat 29 Sep || IFL<br />
|-<br />
|Sun 30 Sep || HW, Scheme<br />
|-<br />
|Mon 1 Oct || ICFP<br />
|-<br />
|Tue 2 Oct || ICFP<br />
|-<br />
|Wed 3 Oct || ICFP<br />
|-<br />
|Thu 4 Oct || CUFP, MM<br />
|-<br />
|Fri 5 Oct || '''Hac 2007 II''', Erlang, ML, PV<br />
|-<br />
|Sat 6 Oct || '''Hac 2007 II'''<br />
|-<br />
|Sun 7 Oct || '''Hac 2007 II'''<br />
|}<br />
<br />
The Hackathon will, ''tentatively'', be held from 10am to 6pm each day,<br />
with dinner after at local venues.<br />
<br />
== Facilities ==<br />
<br />
=== What to bring ===<br />
<br />
* A laptop<br />
* Wireless cards<br />
* Power adaptors if necessary<br />
* Ethernet cable<br />
* Mobile phone<br />
<br />
=== Before you arrive ===<br />
<br />
* Pick out a couple of projects to work on and familiarise yourself with them<br />
* Install an up to date Haskell toolchain (ghc-6.6.1 and if you like a recent snapshot of ghc-6.8.0 also).<br />
<br />
== Projects to work on ==<br />
<br />
Add ideas here for which you think hacking together as a group (rather<br />
than individually) would be beneficial.<br />
<br />
=== Group projects ===<br />
<br />
* Building tests that give 100% code coverage for package base.<br />
* Lots of Cabal hacking still to be done<br />
* Bindings for <your favourite C library><br />
* Haskell library for <your favourite task><br />
* Ensure hackage is ready for ghc 6.8<br />
<br />
=== Other things ===<br />
<br />
* Bit layer on Data.Binary 1.0<br />
* libxml<br />
* bytestring parsec<br />
* combine strictcheck and quickcheck once and for all<br />
* darcs hacking<br />
* aggressive inlining for mtl?<br />
* Data.ByteString.Sequence - a ropes-alike lib based on specialised finger trees<br />
* Data.ByteString.Rope, based on<br />
* [http://www.sgi.com/tech/stl/ropeimpl.html SGIs ropes] or [http://groups.google.com/group/fa.caml/browse_frm/thread/4e70beff0f714229/ new ocaml ropes]<br />
* bit parsing layer for Data.Binary and a network protocol demo?<br />
* dons: HPC coverage for bytestring 1.0<br />
* pretty printer-based ncurses interface<br />
* integrate darcs-piegraph and darcs-graph<br />
* improve the performance of DiffArray using modern techniques [http://www.lri.fr/~filliatr/ftp/ocaml/ds/parray.ml.html OCaml impl]. <br />
** vincenz: Note that even underneath the hood, the ocaml impl is using impurity to implement this (namely the modification of the array in Diff)<br />
* New [http://www.cse.unsw.edu.au/~dons/hs-plugins hs-plugins] on top of ghc-api. [[User:Conal|Conal]]<br />
* Fast general, pure-Haskell image synthesis (speed of [http://conal.net/Pan Pan] or [http://conal.net/Pajama Pajama] but via ghc). Use Harpy or a new hs-plugins. [[User:Conal|Conal]] <br />
* [http://tiddlywiki.com TiddlyWiki]-based code & documentation browser. Syntax-colored and all identifiers fully hyperlinked to sources. Thanks to TiddlyWiki, the browsing experience is fluid & self-organizing. [[User:Conal|Conal]]<br />
* Fix the Network.Socket API (at least to allow <code>setSocketOption x RecvTimeOut</code> and <code>SendTimeOut</code>)<br />
* Haskell WSGI (http://www.python.org/dev/peps/pep-0333/) equivalent with a reference server implementation.<br />
* [http://haskell.org/haskellwiki/UnicodeByteString UnicodeByteString] layer (<code>Text.UnicodeString</code> maybe).<br />
* ByteString network API.<br />
* ByteString simple HTTP<br />
* Library to allow Haskell to communicate with Erlang processes using the Erlang message protocol.<br />
* A better curses rss client than snownews: support ^L resize signal, and parallel feed downloading.<br />
* benl23: Optimize new graph colouring register allocator.<br />
* jutaro: Information extraction for a Haskell IDE (Types,Completion,Navigation)<br />
* ivant: fix [http://cryp.to/funcmp/ Functional MetaPost] (figure out the problems of using it from LaTeX, add definitions for using it from ConTeXt, etc.)<br />
* Possibility to turn logging on/off in lambdabot per channel<br />
* Continuous build system, via as simple, general dependency tracking & execution formulated as an [[applicative functor]] and using [[DataDriven]] computation. No "make" info required (since inferred by construction). Applies uniformly to recompiling, re-executing, installing, compiler-recompiling, GUI specification and execution, etc. For compilation, it can give more precise (efficient) recompilation than language-specific tools (e.g., <code>hmake</code> and <code>ghc --make</code>) without being language-specific. [[User:Conal|Conal]] 13:51, 1 October 2007 (UTC)<br />
<br />
== Organisers ==<br />
<br />
The organisers for the Hackathon are:<br />
<br />
* [http://progtools.comlab.ox.ac.uk/members/duncan Duncan Coutts]<br />
* [mailto:igloo@earth.li Ian Lynagh]<br />
* [http://www.cse.unsw.edu.au/~dons Don Stewart] <br />
<br />
The organisers can be contacted via: <br />
<br />
dons.hac07@cse.unsw.edu.au<br />
<br />
The local organisers in Freiburg:<br />
<br />
* [http://www.informatik.uni-freiburg.de/~wehr/ Stefan Wehr] <br />
* Phillip Heidegger<br />
<br />
Courtesy of the<br />
[http://proglang.informatik.uni-freiburg.de/ICFP2007/local-organizers.shtml Programming Languages Group] at the University of Freiburg.<br />
<br />
== IRC channel ==<br />
<br />
A Hackathon [[IRC channel]] has been set up. Visit:<br />
<br />
#haskell-hac07<br />
<br />
on Freenode.<br />
<br />
== Previous Haskell hackathons ==<br />
<br />
* [[Hac_2007|Hac 2007 - Oxford]]<br />
* [http://hackage.haskell.org/trac/ghc/wiki/Hackathon Hac 2006 - Portland]<br />
<br />
== Related events ==<br />
<br />
Hac 07 II is (unofficially) colocated with ICFP and other conferences:<br />
<br />
{|<br />
!<br />
!<br />
|-<br />
| [http://proglang.informatik.uni-freiburg.de/IFL2007/ IFL]<br />
| September 27-29<br />
|-<br />
| [http://www.cse.unsw.edu.au/~keller/haskellws/HaskellWorkshop.html Haskell Workshop]<br />
| September 30<br />
|-<br />
| [http://www.informatik.uni-bonn.de/~ralf/icfp07.html ICFP] <br />
| October 1-3<br />
|-<br />
| [http://cufp.galois.com/ CUFP] <br />
| October 4<br />
|-<br />
|}<br />
<br />
== Questions ==<br />
<br />
* AJG: What can Galois do to help?<br />
* If there's anything that Credit Suisse can do to support the Hackathon, please let me know - [mailto:howard.mansell@credit-suisse.com]<br />
<br />
== Misc ==<br />
<br />
The Freiburg background is [http://en.wikipedia.org/wiki/Image:Friburgo_-_Freiburg.jpg available] under the GNU Free Documentation License, from wikipedia.<br />
<br />
[[Category:Community]]<br />
[[Category:Events]]</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Hac_2007_II/Projects&diff=16058Hac 2007 II/Projects2007-10-06T09:37:56Z<p>Mnislaih: </p>
<hr />
<div>= Generic Information =<br />
<br />
You can apply for an account and a project using<br />
[http://community.haskell.org/admin/ the community server]. Ping Igloo on #haskell-hac07 and he'll create the account. You can also apply for a project.<br />
<br />
Once you have an account and a project, you upload a Darcs repository as follows. First, initialize your repository on the server:<br />
<br />
$ ssh community.haskell.org<br />
you@haskell:~$ cd /srv/code/yourproject<br />
you@haskell:/srv/code/yourproject$ darcs init<br />
<br />
Then, log out and push your repository:<br />
<br />
$ darcs push community.haskell.org:/srv/code/yourproject<br />
<br />
= Who knows about what =<br />
<br />
A list of projects you've worked on or know fairly well:<br />
<br />
{| class="wikitable"<br />
! Name<br />
! Projects<br />
|-<br />
| dons<br />
| ByteString, xmonad, Data.Binary, lambdabot, hmp3, curses, QuickCheck, HPC, hs-plugins, yi, nobench/nofib, ghc<br />
|-<br />
| Binkley<br />
| ghc, darcs (a little bit)<br />
|-<br />
| skogsbaer (Stefan Wehr)<br />
| hscurses, rhaskell<br />
|-<br />
| Pepe<br />
| ghc (front end mostly), ghci debugger, cabal-install (very little)<br />
|-<br />
| ivant<br />
| Functional MetaPost, xmonad<br />
|-<br />
| kolmodin (Lennart Kolmodin)<br />
| Data.Binary, Gentoo Linux, Haste (Haskell Turbo-Edit,a Haskell IDE in Haskell), hackport (hackage for Gentoo), hinotify, dbus-haskell <br />
|-<br />
| Heffalump (Ganesh Sittampalam)<br />
| darcs patch theory<br />
|-<br />
| [[User:Conal|conal]] (Conal Elliott)<br />
| functional reactive programming, [[DataDriven]] evaluation, tangible functional programming, graphics, embedded compilers, applicative functors, wxHaskell<br />
|}<br />
<br />
= Active Projects =<br />
Please feel free to describe your current project here!<br />
<br />
== Cabal ==<br />
<br />
== ByteString network ==<br />
<br />
Change Network.* to use strict ByteStrings instead of Strings. It would also be nice to tidy up the #ifdef mess.<br />
<br />
Current hacker(s): tibbe (Johan Tibell)<br />
<br />
== Data.Binary ==<br />
<br />
updating to 6.8, adding smp parallel testsuite driver.<br />
<br />
Current hackers: dons<br />
<br />
== xmonad ==<br />
<br />
Testing, HPC coverage, code polishing., new layouts<br />
<br />
Current hackers: dons, ganesh, conrad, nomeata, tibbe<br />
<br />
== Probability monads ==<br />
<br />
A really cool existing implementation: [http://web.engr.oregonstate.edu/~erwig/pfp/ Probabilistic functional programming]<br />
<br />
[http://www.randomhacks.net/articles/2007/10/02/probability-monads-at-hac-07-ii Darcs repository and draft paper].<br />
<br />
Things to work on:<br />
<br />
# Get MaybeT into Hackage.<br />
# Is WriterT really the right monad transformer? We want the join and bind operations, but not the rest of the MonadWriter type class.<br />
# Should probabilities be represented as floats, fractions or a type class?<br />
# Can this run fast enough to be useful?<br />
<br />
Done:<br />
<br />
# [http://www.randomhacks.net/tmp/MaybeT/Control-Monad-Maybe.html MaybeT docs] and [http://code.haskell.org/maybet/ Darcs repository]. This should have all the features of [[New_monads/MaybeT]], except for the potentially ambiguous MonadPlus instance.<br />
# [http://code.haskell.org/monadrandom/ MonadRandom] is now documented and packaged.<br />
# The [http://www.randomhacks.net/darcs/probability/ Probability] library:<br />
#* Now builds using external MaybeT and MonadRandom.<br />
<br />
Current hacker(s): ekidd (Eric Kidd)<br />
<br />
== Yi hacking ==<br />
<br />
Yi needs a lot of love and doesn't work out of the box for me. One of the nice thing to try to do is to add the collaborative editing plugin to yi (in the spirit of the [http://gobby.0x539.de/trac/ Gobby editor]).<br />
* vincenz: Definitely would like to add some usability input here regarding Gobby functionality (having used it and having found it lacking in several areas, areas that could be improved through reusing some darcs theory).<br />
* ivant: also need to add unicode support to yi<br />
* vincenz: Move away from System.Filepath to something std supported<br />
* Cabalize the current 'Setup.hs' *Cabal hackers welcome for help*<br />
* Update the regex dependencies to work with the newest one.<br />
* Work splatch into Yi<br />
<br />
Current hacker(s): ivant (Ivan Tarasov), vincenz (Christophe Poucet)<br />
<br />
== Splatch ==<br />
Patching of splices, or otherwise said, a patch-model for working concurrently on one piece of text.<br />
<br />
Current hacker(s): ivant (Ivan Tarasov), vincenz (Christophe Poucet)<br />
<br />
== Tangible functional programming ==<br />
<br />
Some to-do items:<br />
* More built-ins<br />
* Save<br />
* Improved user experience for gestural composition, e.g., drag & drop<br />
* Does it work on MacOS? Linux?<br />
* Sum types<br />
* Code generation via hs-plugins or ghc-api or Harpy.<br />
<br />
Current hacker(s): [[User:Conal|conal]]<br />
<br />
== General composition tools ==<br />
<br />
=== Type composition & related ===<br />
<br />
[[TypeCompose]]: some classes & instances for forms of type composition (including contravariant functors and applicative functors)<br />
<br />
Current hacker(s): [[User:Conal|conal]]<br />
<br />
=== Deep arrows ===<br />
<br />
[[DeepArrow]]: a framework for composable "editors" of pure values<br />
<br />
Current hacker(s): [[User:Conal|conal]]<br />
<br />
== Source browsing ==<br />
<br />
[http://tiddlywiki.com TiddlyWiki]-based code & documentation browser. Syntax-colored and all identifiers fully hyperlinked to sources. Thanks to TiddlyWiki, the browsing experience is fluid & self-organizing.<br />
<br />
Bring together disparate functionality from HsColour & Haddock, and add auto-generated hyperlinking. Apply to all the code on Hackage.<br />
<br />
Current hacker(s): [[User:Conal|conal]]<br />
<br />
== Graphics ==<br />
<br />
Fast general, pure-Haskell image synthesis (speed of [http://conal.net/Pan Pan] or [http://conal.net/Pajama Pajama] but via ghc). Use Harpy or a new hs-plugins.<br />
<br />
Current hacker(s): [[User:Conal|conal]]<br />
<br />
== General dependency tracking & updating ==<br />
<br />
Simple, general dependency tracking & execution formulated as an [[applicative functor]] and using [[DataDriven]] computation. Applies uniformly to recompiling, re-executing, installing, compiler-recompiling, GUI specification and execution, etc. For compilation, it can give more precise (efficient) recompilation than language-specific tools (e.g., <code>hmake</code> and <code>ghc --make</code>) without being language-specific. Yields a continuous build system for free. No "make" info required (since inferred by construction). (Nontrivial language changes/improvements may be necessary.)<br />
<br />
Current hacker(s): [[User:Conal|conal]]<br />
<br />
== Backtraces in the GHCi debugger ==<br />
<br />
This has turned out to be really complicated, so look at [http://hackage.haskell.org/trac/ghc/wiki/LightweightCCSCallStack here] for the details. Sadly, Alexey stays only for the first day.<br />
<br />
Current hackers: pepe, Alexey</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Hac_2007_II/Attendees&diff=16008Hac 2007 II/Attendees2007-10-05T10:09:58Z<p>Mnislaih: </p>
<hr />
<div>[[Image:Hac-axe-icon.png|Hac icon]]<br />
<br />
== Projects ==<br />
<br />
A list of projects you've worked on or know fairly well:<br />
<br />
{| class="wikitable"<br />
! Name<br />
! Projects<br />
|-<br />
| dons<br />
| ByteString, xmonad, Data.Binary, lambdabot, hmp3, curses, QuickCheck, HPC, hs-plugins, yi, nobench/nofib, ghc<br />
|-<br />
| Binkley<br />
| ghc, darcs (a little bit)<br />
|-<br />
| skogsbaer (Stefan Wehr)<br />
| hscurses, rhaskell<br />
|-<br />
| Pepe<br />
| ghc (front end mostly), ghci debugger, cabal-install (very little)<br />
|-<br />
|}<br />
<br />
<br />
== Registrants ==<br />
<br />
If you've registered, do add your name to the following table:<br />
<br />
{| class="wikitable"<br />
! Name<br />
! Nick<br />
! Affiliiation<br />
! Provided tshirt size<br />
! Mobile #<br />
|-<br />
| [http://www.cse.unsw.edu.au/~dons Don Stewart]<br />
| dons<br />
| Galois<br />
| Yes<br />
|<br />
|-<br />
| Ian Lynagh<br />
| Igloo<br />
|<br />
| Yes<br />
|<br />
|-<br />
| Duncan Coutts<br />
| dcoutts<br />
| Oxford<br />
| Yes<br />
|<br />
|-<br />
| Lennart Kolmodin<br />
| kolmodin<br />
| Chalmers<br />
| Yes<br />
| +46736223606<br />
|-<br />
| Pepe Iborra<br />
| mnislaih<br />
| UPV<br />
| Yes<br />
|<br />
|-<br />
| Ben Lippmeier<br />
| benl23<br />
| ANU<br />
| Yes<br />
|<br />
|-<br />
| David Himmelstrup<br />
| Lemmih<br />
|<br />
| Yes<br />
|<br />
|- <br />
| [http://www.bringert.net/ Björn Bringert]<br />
| bringert<br />
| Chalmers <br />
| Yes<br />
| +46704779794<br />
|-<br />
| Tim Chevalier<br />
| Binkley<br />
| PSU<br />
| Yes<br />
|<br />
|-<br />
| Andy Gill<br />
| andyjgill<br />
| Galois<br />
| Yes<br />
|<br />
|-<br />
| Clemens Fruhwirth<br />
| therp<br />
| <br />
| Yes<br />
|<br />
|-<br />
| Thorkil Naur<br />
| naur<br />
|<br />
| Yes<br />
|<br />
|-<br />
| Benedikt Schmidt<br />
| beschmi<br />
|<br />
| Yes<br />
|<br />
|-<br />
| Thomas Schilling<br />
| nominolo<br />
|<br />
| Yes<br />
|<br />
|-<br />
| Conal Elliott<br />
| conal<br />
|<br />
| Yes<br />
|<br />
|-<br />
| Russell O'Connor<br />
| roconnor<br />
|<br />
| Yes<br />
| +31625178046<br />
|-<br />
| Ganesh Sittampalam<br />
| Heffalump<br />
| Credit Suisse<br />
| Yes<br />
|<br />
|-<br />
| Jürgen Nicklisch<br />
| Jutaro<br />
|<br />
| Yes<br />
|<br />
|-<br />
| Ivan Tarasov<br />
| ivant<br />
|<br />
| Yes<br />
|<br />
|-<br />
| Johan Tibell<br />
| tibbe<br />
|<br />
| Yes<br />
|<br />
|-<br />
| Clifford Beshers<br />
| thetallguy<br />
|<br />
| Yes<br />
|<br />
|-<br />
| David Fox<br />
| dsf<br />
| <br />
| Yes<br />
|<br />
|-<br />
| [http://www.esat.kuleuven.ac.be/~cpoucet Christophe Poucet]<br />
| vincenz<br />
| IMEC<br />
| Yes<br />
|<br />
|-<br />
| Matthias Neubauer<br />
| heckenpenner<br />
| Freiburg<br />
| Yes<br />
|<br />
|-<br />
| Stefan Wehr<br />
| <br />
| Freiburg<br />
| Yes<br />
|<br />
|-<br />
| [http://www.randomhacks.net/ Eric Kidd]<br />
| ekidd<br />
| Dartmouth<br />
| Yes<br />
| 15776874941<br />
|-<br />
| Marcus Uneson<br />
| muneson<br />
| <br />
| Yes<br />
|<br />
|-<br />
| Conrad Barski<br />
| drcode<br />
| <br />
| Yes<br />
| [http://lisperati.com/haskell/ My Brand New Haskell Tutorial :-)]<br />
|-<br />
| Joachim Breitner<br />
| nomeata<br />
| <br />
| Yes<br />
|<br />
|}<br />
<br />
== Arriving ==<br />
<br />
===Train===<br />
<br />
* Igloo: 29 Sep at 21:00, Freiburg Hbf.<br />
* Lemmih: 29 Sep at 18:00, Freiburg Hbf.<br />
* Jutaro: 29 Sep at 23:09, Freiburg Hbf.<br />
* ivant: 30 Sep, at 8:00, from Vienna<br />
* tibbe: 5 Oct, at 8:00, from Zurich<br />
* vincenz: 4 Oct, At 23-24, Freiburg Hbf.<br />
* roconnor: 4 Oct, at 21:00, Freiburg Hbf.<br />
<br />
===Air===<br />
<br />
* Andy Gill, 29 Sep Frankfurt<br />
* Don Stewart, 29 Sep 8.35 am, Frankfurt<br />
* Thomas Schilling, 29 Sep Frankfurt Main<br />
* Conal Elliott, 25 Sep 11:10 am, Frankfurt<br />
* Ganesh Sittampalam, 29 Sep 2:50 pm, Zurich<br />
* Pepe Iborra, 29 Sep 8:40 pm, Frankfurt Hahn (HHN)<br />
* Lennart Kolmodin, 29 Sep, 12:05, Frankfurt<br />
* Björn Bringert, 04 Oct 18:55, Frankfurt (train to Freiburg dep 19.54, arr 22:15)<br />
<br />
== Accomodation ==<br />
<br />
A number of accommodation options are available. To organize to share,<br />
contact other attendees on irc or via email. <br />
<br />
=== Black Forest Hostel ===<br />
<br />
Some people are staying at the hostel: http://www.blackforest-hostel.de/<br />
<br />
* Igloo, Lemmih, nominolo: 29 Sep - 8 Oct<br />
* conal: same, in a 6-bed dorm room, 25 Sep - 8 Oct<br />
* ivant: same, 30 Sep - 8 Oct<br />
* tibbe: 6-bed dorm room, 5 Oct - 7 Oct<br />
* mnislaih: same<br />
* dcoutts, kolmodin: 6-bed dorm room, 29 Sep - 8 Oct<br />
* drcode<br />
* roconnor: dorm room, 4 Oct - 8 Oct (still to be confirmed)<br />
<br />
We will be meeting at 9am at the entrance of the Black Forest Hostel to go to the Hackathon venue.<br />
<br />
=== Best Western ===<br />
<br />
* dons, andy: Best Western<br />
<br />
=== InterCityHotel ===<br />
<br />
http://www.booking.com/hotel/de/intercityhotelfreiburg.html<br />
<br />
* bringert, vincenz: 04 Oct - 07 Oct<br />
<br />
=== Paradies ===<br />
<br />
* jutaro: 01 Oct - 07 Oct</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Traits_type_class&diff=15650Traits type class2007-09-18T12:36:05Z<p>Mnislaih: </p>
<hr />
<div>Occasionally you want to associate information with a [[type]], not just a value. An example is the standard <hask>Bounded</hask> class:<br />
<br />
<haskell><br />
class Bounded a where<br />
minBound :: a<br />
maxBound :: a<br />
</haskell><br />
<br />
However, this technique does not work if the information which you want to extract doesn't have the type in its signature. One example is floating point format information, such as:<br />
<br />
<haskell><br />
class FloatTraits a where<br />
-- This one is fine<br />
epsilon :: a<br />
-- This one is not<br />
mantissaDigits :: Int<br />
-- etc<br />
</haskell><br />
<br />
The problem is that there is simply no way to tell Haskell which version of <hask>mantissaDigits</hask> you want, because the [[Type parameter]] a does not appear in its type signature anywhere.<br />
<br />
The solution is to pass a [[Reified type]] as a phantom argument:<br />
<br />
<haskell><br />
class FloatTraits a where<br />
mantissaDigits :: a -> Int<br />
<br />
instance FloatTraits Float where<br />
mantissaDigits _ = 24<br />
<br />
instance FloatTraits Double where<br />
mantissaDigits _ = 53<br />
</haskell><br />
<br />
You can then use the version you want by passing the <hask>undefined</hask> value cast to a specific type:<br />
<br />
<code><br />
HaskellPrompt> mantissaDigits (undefined :: Float)<br />
24<br />
</code><br />
<br />
This technique works well in conjunction with [[Functional Dependancy]]. For example, there may be some float types for which an Int may not be sufficient to express the number of digits in the mantissa:<br />
<br />
<haskell><br />
class (Integral i) => FloatTraits a i | a -> i where<br />
mantissaDigits :: a -> i<br />
<br />
instance FloatTraits Float Int where<br />
mantissaDigits _ = 24<br />
<br />
instance FloatTraits ArbitraryPrecisionFloat Integer where<br />
mantissaDigits x = {- detail omitted -}<br />
</haskell><br />
<br />
You can also use this technique as an alternative to [[Higher order function]]s in cases where you need several functions which work together.<br />
<br />
Consider, for example, converting strings from upper case to lower case and back again. This in general depends on the language that you are operating in. The lower case version of 'A', for example, is different in English than in Greek. You can wrap this up in a typeclass parameterised on language:<br />
<br />
<haskell><br />
class CaseConvert language where<br />
toUpperCase :: language -> String -> String<br />
toLowerCase :: language -> String -> String<br />
<br />
data EnglishLanguage = EnglishLanguage<br />
<br />
instance CaseConvert EnglishLanguage where<br />
toUpperCase _ s = {- etc -}<br />
toLowerCase _ s = {- etc -}<br />
<br />
data GreekLanguage = GreekLanguage<br />
<br />
instance CaseConvert GreekLanguage where<br />
toUpperCase _ s = {- etc -}<br />
toLowerCase _ s = {- etc -}<br />
</haskell><br />
<br />
This way, you only need pass around one "language" parameter rather than two [[Higher order function]]s.<br />
<br />
[[User:AndrewBromage]]<br />
<br />
A very nice example by Lennart is found in his [http://augustss.blogspot.com/2007/04/overloading-haskell-numbers-part-3.html blog]<br />
<br />
[[Category:Idioms]]</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Hac_2007_II/Attendees&diff=15440Hac 2007 II/Attendees2007-09-07T11:06:58Z<p>Mnislaih: </p>
<hr />
<div>[[Image:Hac-axe-icon.png|Hac icon]]<br />
<br />
== Registrants ==<br />
<br />
If you've registered, do add your name to the following table.:<br />
<br />
{| class="wikitable"<br />
! Number<br />
! Name<br />
! Nick<br />
! Affiliiation<br />
|-<br />
| 1<br />
| Don Stewart<br />
| dons<br />
| Galois<br />
|-<br />
| 2<br />
| Ian Lynagh<br />
| Igloo<br />
|<br />
|-<br />
| 3<br />
| Duncan Coutts<br />
| dcoutts<br />
| Oxford<br />
|-<br />
| 4<br />
| Malcolm Wallace<br />
| malcolmw<br />
|<br />
|-<br />
| 5<br />
| Lennart Kolmodin<br />
| kolmodin<br />
| Chalmers<br />
|-<br />
| 6<br />
| Pepe Iborra<br />
| mnislaih<br />
| UPV<br />
|-<br />
| 7<br />
| Ben Lippmeier<br />
| benl23<br />
| ANU<br />
|-<br />
| 8<br />
| David Himmelstrup<br />
| Lemmih<br />
|<br />
|- <br />
| 9<br />
| Bjrn Bringert<br />
| bringert<br />
| Chalmers <br />
|-<br />
| 10<br />
| David Waern<br />
| waern<br />
|<br />
|-<br />
| 11<br />
| Rickard Nilsson<br />
| ricky<br />
|<br />
|-<br />
| 12<br />
| Tim Chevalier<br />
| Binkley<br />
|<br />
|-<br />
| 13<br />
| Neil Mitchell<br />
| ndm<br />
|<br />
|-<br />
| 14<br />
| Andy Gill<br />
| andyjgill<br />
| Galois<br />
|-<br />
| 15<br />
| Clemens Fruhwirth<br />
| therp<br />
|<br />
|-<br />
| 16<br />
| Thorkil Naur<br />
| naur<br />
|<br />
|-<br />
| 17<br />
| Benedikt Schmidt<br />
| beschmi<br />
|<br />
|-<br />
|18<br />
| Thomas Schilling<br />
| nominolo<br />
|<br />
|-<br />
|19<br />
| Conal Elliott<br />
| conal<br />
|<br />
|-<br />
|20<br />
| Russell O'Connor<br />
| roconnor<br />
|<br />
|-<br />
|21<br />
| Ganesh Sittampalam<br />
| Heffalump<br />
| Credit Suisse<br />
|-<br />
|22<br />
| Jürgen Nicklisch<br />
| Jutaro<br />
| <br />
|-<br />
|23<br />
| Ivan Tarasov<br />
| ivant<br />
|<br />
|-<br />
|24<br />
| Johan Tibell<br />
| tibbe<br />
| <br />
|-<br />
|}<br />
<br />
== Arriving ==<br />
<br />
===Train===<br />
<br />
* Igloo: By train, 29 Sep at 21:00, Freiburg Hbf.<br />
* Lemmih: By train, 29 Sep at 18:00, Freiburg Hbf.<br />
* ivant: By train, 30 Sep, at 8:00, from Vienna<br />
* tibbe: By train, 5 Oct, at 8:00, from Zurich<br />
<br />
===Air===<br />
<br />
* Andy Gill, 29 Sep Frankfurt<br />
* Don Stewart, 29 Sep 8.35 am, Frankfurt<br />
* Thomas Schilling, 29 Sep Frankfurt Main<br />
* Conal Elliott, 25 Sep 11:10 am, Frankfurt<br />
* Ganesh Sittampalam, 29 Sep 2:50 pm, Zurich<br />
* Pepe Iborra, 29 Sep 8:40 pm, Frankfurt Hahn (HHN)<br />
<br />
== Accomodation ==<br />
<br />
A number of accommodation options are available. To organise to share,<br />
contact other attendees on irc or via email. <br />
<br />
* Igloo & Lemmih: http://www.blackforest-hostel.de/ 29 Sep - 8 Oct<br />
* nominolo: same<br />
* conal: same, in a 6-bed dorm room, 25 Sep - 8 Oct<br />
* ivant: hopefully, same, 30 Sep — 8 Oct<br />
* tibbe: same, haven't made a reservation yet, 5 Oct - 7 Oct<br />
* mnislaih: same</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Hac_2007_II/Attendees&diff=15439Hac 2007 II/Attendees2007-09-07T11:06:28Z<p>Mnislaih: Arriving & Acommodation details</p>
<hr />
<div>[[Image:Hac-axe-icon.png|Hac icon]]<br />
<br />
== Registrants ==<br />
<br />
If you've registered, do add your name to the following table.:<br />
<br />
{| class="wikitable"<br />
! Number<br />
! Name<br />
! Nick<br />
! Affiliiation<br />
|-<br />
| 1<br />
| Don Stewart<br />
| dons<br />
| Galois<br />
|-<br />
| 2<br />
| Ian Lynagh<br />
| Igloo<br />
|<br />
|-<br />
| 3<br />
| Duncan Coutts<br />
| dcoutts<br />
| Oxford<br />
|-<br />
| 4<br />
| Malcolm Wallace<br />
| malcolmw<br />
|<br />
|-<br />
| 5<br />
| Lennart Kolmodin<br />
| kolmodin<br />
| Chalmers<br />
|-<br />
| 6<br />
| Pepe Iborra<br />
| mnislaih<br />
| UPV<br />
| <br />
|-<br />
| 7<br />
| Ben Lippmeier<br />
| benl23<br />
| ANU<br />
|-<br />
| 8<br />
| David Himmelstrup<br />
| Lemmih<br />
|<br />
|- <br />
| 9<br />
| Bjrn Bringert<br />
| bringert<br />
| Chalmers <br />
|-<br />
| 10<br />
| David Waern<br />
| waern<br />
|<br />
|-<br />
| 11<br />
| Rickard Nilsson<br />
| ricky<br />
|<br />
|-<br />
| 12<br />
| Tim Chevalier<br />
| Binkley<br />
|<br />
|-<br />
| 13<br />
| Neil Mitchell<br />
| ndm<br />
|<br />
|-<br />
| 14<br />
| Andy Gill<br />
| andyjgill<br />
| Galois<br />
|-<br />
| 15<br />
| Clemens Fruhwirth<br />
| therp<br />
|<br />
|-<br />
| 16<br />
| Thorkil Naur<br />
| naur<br />
|<br />
|-<br />
| 17<br />
| Benedikt Schmidt<br />
| beschmi<br />
|<br />
|-<br />
|18<br />
| Thomas Schilling<br />
| nominolo<br />
|<br />
|-<br />
|19<br />
| Conal Elliott<br />
| conal<br />
|<br />
|-<br />
|20<br />
| Russell O'Connor<br />
| roconnor<br />
|<br />
|-<br />
|21<br />
| Ganesh Sittampalam<br />
| Heffalump<br />
| Credit Suisse<br />
|-<br />
|22<br />
| Jürgen Nicklisch<br />
| Jutaro<br />
| <br />
|-<br />
|23<br />
| Ivan Tarasov<br />
| ivant<br />
|<br />
|-<br />
|24<br />
| Johan Tibell<br />
| tibbe<br />
| <br />
|-<br />
|}<br />
<br />
== Arriving ==<br />
<br />
===Train===<br />
<br />
* Igloo: By train, 29 Sep at 21:00, Freiburg Hbf.<br />
* Lemmih: By train, 29 Sep at 18:00, Freiburg Hbf.<br />
* ivant: By train, 30 Sep, at 8:00, from Vienna<br />
* tibbe: By train, 5 Oct, at 8:00, from Zurich<br />
<br />
===Air===<br />
<br />
* Andy Gill, 29 Sep Frankfurt<br />
* Don Stewart, 29 Sep 8.35 am, Frankfurt<br />
* Thomas Schilling, 29 Sep Frankfurt Main<br />
* Conal Elliott, 25 Sep 11:10 am, Frankfurt<br />
* Ganesh Sittampalam, 29 Sep 2:50 pm, Zurich<br />
* Pepe Iborra, 29 Sep 8:40 pm, Frankfurt Hahn (HHN)<br />
<br />
== Accomodation ==<br />
<br />
A number of accommodation options are available. To organise to share,<br />
contact other attendees on irc or via email. <br />
<br />
* Igloo & Lemmih: http://www.blackforest-hostel.de/ 29 Sep - 8 Oct<br />
* nominolo: same<br />
* conal: same, in a 6-bed dorm room, 25 Sep - 8 Oct<br />
* ivant: hopefully, same, 30 Sep — 8 Oct<br />
* tibbe: same, haven't made a reservation yet, 5 Oct - 7 Oct<br />
* mnislaih: same</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Performance/Monads&diff=14640Performance/Monads2007-07-24T08:47:19Z<p>Mnislaih: </p>
<hr />
<div>{{Performance infobox}}<br />
[[Category:Performance|Monads]]<br />
== Unroll your MTL stacks ==<br />
<br />
MTL is an excellent library for programming with monads. However stacked monad transformers do not inline well and the library is in need of an optimization pass. As a result, it can often impose a performance hit of up to 300% (your code will run up to three times slower). <br />
<br />
If you care about this, the best option is to flatten you stack of transformers into a single, hand unrolled monad. An extreme example follows.<br />
<br />
This is a typical MTL monad stack<br />
<br />
newtype DRM a = DRM {unDRM:: ErrorT Finish (RWS () DNA RNA) a}<br />
deriving (MonadState DNA, MonadWriter RNA, MonadError Finish, Monad)<br />
<br />
We can unroll it as follows:<br />
<br />
<haskell><br />
type DRM = DRMonad Finish DNA RNA<br />
newtype DRMonad e s w a = DRMonad {runDRMonad :: s -> (Either e a,s,w)}<br />
<br />
instance (Monoid m, Error e) => Monad (DRMonad e s w) where<br />
return x = DRMonad(\s -> (Right x, s, mempty))<br />
(>>= = bindDRMonad<br />
fail _ = DRMonad (\s->(Left e,s,mempty))<br />
<br />
{-# INLINE bindDRMonad #-}<br />
{-# INLINE bindDRMonad2 #-}<br />
bindDRMonad :: Monoid m => DRMonad a e s w -> (a -> DRMonad b e s w) -> DRMonad b e s w<br />
bindDRMonad m f = DRMonad$ \s -> case runDRMonad m s of<br />
(x',s',w) -><br />
bindDRMonad2 x' (s',w,f)<br />
bindDRMonad2 x' (s',w, f) = case x' of <br />
Left e -> (Left e, s', w)<br />
Right r -> case runDRMonad (f r) s' of<br />
(x'',s'',w') -><br />
(x'', s'', w `mappend` w')<br />
</haskell><br />
<br />
After this, you will also want to add the instances for MonadState, MonadWriter, etc.</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Performance/Monads&diff=14639Performance/Monads2007-07-24T08:42:44Z<p>Mnislaih: </p>
<hr />
<div>{{Performance infobox}}<br />
[[Category:Performance|Monads]]<br />
== Unroll your MTL stacks ==<br />
<br />
MTL is an excellent for programming with monads, however stacked monad transformers do not inline well and can often impose a performance hit of up to 300% (your code will run up to three times slower). <br />
<br />
If you care about this, the best option is to flatten you stack of transformers into a single, hand unrolled monad. An extreme example follows.<br />
<br />
This is a typical MTL monad stack<br />
<br />
newtype DRM a = DRM {unDRM:: ErrorT Finish (RWS () DNA RNA) a}<br />
deriving (MonadState DNA, MonadWriter RNA, MonadError Finish, Monad)<br />
<br />
We can unroll it as follows:<br />
<br />
<haskell><br />
type DRM = DRMonad Finish DNA RNA<br />
newtype DRMonad e s w a = DRMonad {runDRMonad :: s -> (Either e a,s,w)}<br />
<br />
instance (Monoid m, Error e) => Monad (DRMonad e s w) where<br />
return x = DRMonad(\s -> (Right x, s, mempty))<br />
(>>= = bindDRMonad<br />
fail _ = DRMonad (\s->(Left e,s,mempty))<br />
<br />
{-# INLINE bindDRMonad #-}<br />
{-# INLINE bindDRMonad2 #-}<br />
bindDRMonad :: Monoid m => DRMonad a e s w -> (a -> DRMonad b e s w) -> DRMonad b e s w<br />
bindDRMonad m f = DRMonad$ \s -> case runDRMonad m s of<br />
(x',s',w) -><br />
bindDRMonad2 x' (s',w,f)<br />
bindDRMonad2 x' (s',w, f) = case x' of <br />
Left e -> (Left e, s', w)<br />
Right r -> case runDRMonad (f r) s' of<br />
(x'',s'',w') -><br />
(x'', s'', w `mappend` w')<br />
</haskell><br />
<br />
After this, you will also want to add the instances for MonadState, MonadWriter, etc.</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Performance/Monads&diff=14638Performance/Monads2007-07-24T08:41:25Z<p>Mnislaih: </p>
<hr />
<div>{{Performance infobox}}<br />
[[Category:Performance|Monads]]<br />
== Unroll your MTL stacks ==<br />
<br />
MTL is an excellent for programming with monads, however stacked monad transformers do not inline well and often impose a performance hit of up to 3X. <br />
<br />
If you care about this, the best option is to flatten you stack of transformers into a single, hand unrolled monad. An extreme example follows.<br />
<br />
This is a typical MTL monad stack<br />
<br />
newtype DRM a = DRM {unDRM:: ErrorT Finish (RWS () DNA RNA) a}<br />
deriving (MonadState DNA, MonadWriter RNA, MonadError Finish, Monad)<br />
<br />
We can unroll it as follows:<br />
<br />
<haskell><br />
type DRM = DRMonad Finish DNA RNA<br />
newtype DRMonad e s w a = DRMonad {runDRMonad :: s -> (Either e a,s,w)}<br />
<br />
instance (Monoid m, Error e) => Monad (DRMonad e s w) where<br />
return x = DRMonad(\s -> (Right x, s, mempty))<br />
(>>= = bindDRMonad<br />
fail _ = DRMonad (\s->(Left e,s,mempty))<br />
<br />
{-# INLINE bindDRMonad #-}<br />
{-# INLINE bindDRMonad2 #-}<br />
bindDRMonad :: Monoid m => DRMonad a e s w -> (a -> DRMonad b e s w) -> DRMonad b e s w<br />
bindDRMonad m f = DRMonad$ \s -> case runDRMonad m s of<br />
(x',s',w) -><br />
bindDRMonad2 x' (s',w,f)<br />
bindDRMonad2 x' (s',w, f) = case x' of <br />
Left e -> (Left e, s', w)<br />
Right r -> case runDRMonad (f r) s' of<br />
(x'',s'',w') -><br />
(x'', s'', w `mappend` w')<br />
</haskell><br />
<br />
After this, you will also want to add the instances for MonadState, MonadWriter, etc.</div>Mnislaihhttps://wiki.haskell.org/index.php?title=ICFP_Programming_Contest/Teams_2007&diff=14636ICFP Programming Contest/Teams 20072007-07-24T08:33:48Z<p>Mnislaih: </p>
<hr />
<div>This page is for helping Haskell (and FP) people organise teams for the<br />
[http://www.icfpcontest.org// 2007 ICFP contest].<br />
<br />
* [http://www.kingsrook.com/icfp/countdown.html Countdown to contest start]<br />
<br />
Resources:<br />
* The home of [http://www.icfpcontest.org/ ICFP 2007].<br />
* The #haskell-icfp07 and #haskell [[IRC channel]]s on freenode.<br />
* The #oasis [[IRC channel]] on freenode: generic ICFP discussion channel (not specifically Haskell oriented)<br />
* [http://article.gmane.org/gmane.comp.lang.haskell.cafe/24773 Announcement] for this page.<br />
<br />
== Teams ==<br />
<br />
Teams that competed and their final rankings.<br />
<br />
{| border="0" cellspacing="15" cellpadding="2"<br />
! Team<br />
! Members<br />
! Ranking<br />
|-<br />
| Basically Awesome<br />
| jcd__ et al<br />
| less than 15<br />
|-<br />
| solo r6<br />
| roconnor<br />
| 32<br />
|-<br />
| Lazy Bottoms<br />
| vincenz, Adept, Lemmih, psykotic, zeeeee, jethr0, Cale<br />
| 56<br />
|-<br />
| Team PDX<br />
| Binkley et al<br />
| 67<br />
|-<br />
| TNT: Team Named Thunk <br />
| timbod, mnislaih, Toxaris{- [http://ender4.dsic.upv.es:81/darcs/tnt code] -}<br />
| 80<br />
|-<br />
| The Church of the Least Fixed Point<br />
| desp, dreamer_, lispozord, q, rraptorr<br />
| 95<br />
|-<br />
| cdsmith<br />
| Chris Smith<br />
| 104<br />
|-<br />
| ChuToys<br />
| genneth, smowton, greg<br />
| 129<br />
|-<br />
| Instant Chaos <br />
| alar @ #haskell, #oasis, #haskell_ru , nealar @livejournal.com<br />
| 133<br />
|-<br />
| augustss<br />
| Lennart<br />
| 151<br />
|-<br />
| scsibug<br />
| Greg Heartsfield<br />
| 195<br />
|-<br />
| Pointless<br />
| nominolo, Igloo, mauke<br />
| 695<br />
|-<br />
|}<br />
<br />
The following teams sound like they might use Haskell, or FP at least:<br />
<br />
{| border="0" cellspacing="15" cellpadding="2"<br />
! Teams that sound like they use Haskell<br />
! Members<br />
! Rank<br />
|-<br />
| PurelyFunctionalInfrastructure (maybe)<br />
| ?<br />
| less than 16<br />
|-<br />
| The Higher order of Zeuxis<br />
| ?<br />
| 16<br />
|-<br />
| Frictionless Bananas<br />
| ?<br />
| 27<br />
|-<br />
| Side Effects May Include... (maybe)<br />
| ?<br />
| 29<br />
|-<br />
| Poor Man's Haskell (maybe)<br />
| ?<br />
| 252<br />
|-<br />
| Haskeller (maybe)<br />
| ?<br />
| 312<br />
|-<br />
| Nomadic I/O<br />
| ?<br />
| 578<br />
|-<br />
|}<br />
<br />
== Contest Code ==<br />
<br />
Some teams have made their contest source code available<br />
<br />
{| border="0" cellspacing="15" cellpadding="2"<br />
! Team<br />
! Respoistory Access<br />
|-<br />
| solo r6<br />
| darcs get http://r6.ca/icfp2007<br />
|-<br />
| Antoine, Creighton <br />
| http://panicsonic.blogspot.com/2007/07/icfp-07-post-mortem-i.html<br />
|- <br />
[[Category:Contest]]</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Performance/Monads&diff=14628Performance/Monads2007-07-24T01:13:00Z<p>Mnislaih: </p>
<hr />
<div>{{Performance infobox}}<br />
[[Category:Performance|Monads]]<br />
== Unroll your MTL stacks ==<br />
<br />
MTL is an excellent for programming with monads, however stacked monad transformers do not inline well and often impose a performance hit of up to 3X. <br />
<br />
If you care about this, the best option is to flatten you stack of transformers into a single, hand unrolled monad. An extreme example follows.<br />
<br />
This is a typical MTL monad stack<br />
<br />
newtype DRM a = DRM {unDRM:: ErrorT Finish (RWS () DNA RNA) a}<br />
deriving (MonadState DNA, MonadWriter RNA, MonadError Finish, Monad)<br />
<br />
We can unroll it as follows:<br />
<br />
<haskell><br />
type DRM = DRMonad<br />
newtype DRMonad a e s w = DRMonad {runDRMonad :: s -> (Either e a,s,w)}<br />
<br />
instance (Monoid m, Error e) => Monad (DRMonad e s w) where<br />
return x = DRMonad(\s -> (Right x, s, mempty))<br />
(>>= = bindDRMonad<br />
fail _ = DRMonad (\s->(Left e,s,mempty))<br />
<br />
{-# INLINE bindDRMonad #-}<br />
{-# INLINE bindDRMonad2 #-}<br />
bindDRMonad :: Monoid m => DRMonad a e s w -> (a -> DRMonad b e s w) -> DRMonad b e s w<br />
bindDRMonad m f = DRMonad$ \s -> case runDRMonad m s of<br />
(x',s',w) -><br />
bindDRMonad2 x' (s',w,f)<br />
bindDRMonad2 x' (s',w, f) = case x' of <br />
Left e -> (Left e, s', w)<br />
Right r -> case runDRMonad (f r) s' of<br />
(x'',s'',w') -><br />
(x'', s'', w `mappend` w')<br />
</haskell><br />
<br />
After this, you will also want to add the instances for MonadState, MonadWriter, etc.</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Performance/Monads&diff=14627Performance/Monads2007-07-24T01:11:33Z<p>Mnislaih: </p>
<hr />
<div>{{Performance infobox}}<br />
[[Category:Performance|Monads]]<br />
== Unroll your MTL stacks ==<br />
<br />
MTL is an excellent for programming with monads, however stacked monad transformers do not inline well and often impose a performance hit of up to 3X. <br />
<br />
If you care about this, the best option is to flatten you stack of transformers into a single, hand unrolled monad. An extreme example follows.<br />
<br />
This is a typical MTL monad stack<br />
<br />
newtype DRM a = DRM {unDRM:: ErrorT Finish (RWS () DNA RNA) a}<br />
deriving (MonadState DNA, MonadWriter RNA, MonadError Finish, Monad)<br />
<br />
We can unroll it as follows:<br />
<br />
<haskell><br />
type DRM = DRMonad<br />
newtype DRMonad a e s w = DRMonad {runDRMonad :: s -> (Either e a,s,w)}<br />
<br />
instance (Monoid m, Error e) => Monad (DRMonad e s w) where<br />
return x = DRMonad(\s -> (Right x, s, mempty))<br />
(>>= = bindDRMonad<br />
fail _ = DRMonad (\s->(Left e,s,mempty))<br />
<br />
{-# INLINE bindDRMonad #-}<br />
{-# INLINE bindDRMonad2 #-}<br />
bindDRMonad :: Monoid m => DRMonad a e s w -> (a -> DRMonad b e s w) -> DRMonad b e s w<br />
bindDRMonad m f = DRMonad$ \s -> case runDRMonad m s of<br />
(x',s',w) -><br />
bindDRMonad2 x' (s',w,f)<br />
bindDRMonad2 x' (s',w, f) = case x' of <br />
Left e -> (Left e, s', w)<br />
Right r -> case runDRMonad (f r) s' of<br />
(x'',s'',w') -><br />
(x'', s'', w `mappend` w')<br />
</haskell></div>Mnislaihhttps://wiki.haskell.org/index.php?title=Performance/Monads&diff=14626Performance/Monads2007-07-24T01:11:08Z<p>Mnislaih: </p>
<hr />
<div>{{Performance infobox}}<br />
[[Category:Performance|Monads]]<br />
== Unroll your MTL stacks ==<br />
<br />
MTL is an excellent for programming with monads, however stacked monad transformers do not inline well and often impose a performance hit of up to 3X. <br />
<br />
If you care about this, the best option is to flatten you stack of transformers into a single, hand unrolled monad. An extreme example follows.<br />
<br />
This is a typical MTL monad stack<br />
<br />
newtype DRM a = DRM {unDRM:: ErrorT Finish (RWS () DNA RNA) a}<br />
deriving (MonadState DNA, MonadWriter RNA, MonadError Finish, Monad)<br />
<br />
We can unroll it as follows:<br />
<br />
<haskell><br />
type DRM = DRMonad<br />
newtype DRMonad a e s w = DRMonad {runDRMonad :: s -> (Either e a,s,w)}<br />
<br />
instance (Monoid m, Error e) => Monad (DRMonad e s w) where<br />
return x = DRMonad(\s -> (Right x, s, mempty))<br />
(>>= = bindDRMonad<br />
fail _ = DRMonad (\s->(Left e,s,mempty))<br />
<br />
{-# INLINE bindDRMonad #-}<br />
{-# INLINE bindDRMonad2 #-}<br />
bindDRMonad :: (Monoid m) =>DRMonad a e s w -> (a -> DRMonad b e s w) -> DRMonad b e s w<br />
bindDRMonad m f = DRMonad$ \s -> case runDRMonad m s of<br />
(x',s',w) -><br />
bindDRMonad2 x' (s',w,f)<br />
bindDRMonad2 x' (s',w, f) = case x' of <br />
Left e -> (Left e, s', w)<br />
Right r -> case runDRMonad (f r) s' of<br />
(x'',s'',w') -><br />
(x'', s'', w `mappend` w')<br />
</haskell></div>Mnislaihhttps://wiki.haskell.org/index.php?title=Template:Performance_infobox&diff=14625Template:Performance infobox2007-07-24T01:08:07Z<p>Mnislaih: </p>
<hr />
<div>{| class="wikitable" align="right"<br />
|-<br />
| style="padding: 1em 1em 0 1em;" align="center" | '''[[Performance|Haskell Performance Resource]]'''<br />
''Constructs'':<br/>[[Performance/Data types | Data Types]] - [[Performance/Functions | Functions]]<br/>[[Performance/Overloading | Overloading]] - [[Performance/FFI | FFI]] - [[Performance/Arrays | Arrays]]<br/>[[Performance/Strings | Strings]] - [[Performance/Integers | Integers]] - [[Performance/IO | I/O ]]<br/>[[Performance/Floating point | Floating point]] - [[Performance/Concurrency | Concurrency]]<br/>[[Performance/Modules | Modules]] - [[Performance/Monads | Monads]]<br />
<br />
''Techniques'':<br/>[[Performance/Strictness | Strictness]] - [[Performance/Laziness | Laziness]]<br/>[[Performance/Space | Avoiding space leaks]] <br/><br />
[[Performance/Accumulating parameter | Accumulating parameter ]]<br />
<br />
''Implementation-Specific'':<br/>[[Performance/GHC| GHC]] - [[Performance/NHC98| nhc98]] - [[Performance/Hugs| Hugs]]<br/>[[Performance/Yhc| Yhc]] - [[Performance/JHC| JHC]]<br />
|}</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Performance&diff=14624Performance2007-07-24T01:06:06Z<p>Mnislaih: </p>
<hr />
<div>{{Performance infobox}}<br />
Welcome to the '''Haskell Performance Resource''', the collected wisdom on how to make your Haskell programs go faster. <br />
<br />
== Introduction ==<br />
<br />
In most cases it is possible to write a Haskell program that performs as well as, or better than, the same program written in [''insert language here'']. There's a big caveat though: you may have to modify your code significantly in order to improve its performance. Compilers such as GHC are good at eliminating layers of abstraction, but they aren't perfect, and often need some help. <br />
<br />
There are many non-invasive techniques: compiler options, for example. Then there are techniques that require adding some small amounts of performance cruft to your program: strictness annotations, for example. If you still don't get the best performance, though, it might be necessary to resort to larger refactorings.<br />
<br />
Sometimes the code tweaks required to get the best performance are non-portable, perhaps because they require language extensions that aren't implemented in all compilers (eg. unboxing), or because they require using platform-specific features or libraries. This might not be acceptable in your setting.<br />
<br />
If the worst comes to the worst, you can always write your critical code in C and use the FFI to call it. Beware of the boundaries though - marshaling data across the FFI can be expensive, and multi-language memory management can be complex and error-prone. It's usually better to stick to Haskell if possible.<br />
<br />
== Basic techniques ==<br />
<br />
The key tool to use in making your Haskell program run faster is ''profiling''. Profiling is provided by [[GHC]] and [[nhc98]]. There is ''no substitute'' for finding where your program's time/space is ''really'' going, as opposed to where you imagine it is going.<br />
<br />
Another point to bear in mind: By far the best way to improve a program's performance ''dramatically'' is to use better algorithms. Once profiling has thrown the spotlight on the guilty time-consumer(s), it may be better to re-think your program than to try all the tweaks listed below.<br />
<br />
Another extremely efficient way to make your program snappy is to use library code that has been Seriously Tuned By Someone Else. You ''might'' be able to write a better quicksort than the one in <tt>Data.List</tt> but it<br />
will take you much longer than typing <tt>import Data.List</tt>.<br />
<br />
We have chosen to organise the rest of this resource first by Haskell construct (data types, pattern matching, integers), and then within each category to describe techniques that apply across implementations, and also techniques that are specific to a certain Haskell implementation (eg. GHC). There are some implementation-specific tecniques that apply in general - those are linked from the [[Haskell Performance Resource#General_Implementation-Specific_Techniques | General Implementation-Specific Techniques]] section below.<br />
<br />
== Haskell constructs ==<br />
<br />
* [[/Data Types/]]<br />
* [[/Functions/]]<br />
* [[/Overloading/]]<br />
* [[/FFI/]]<br />
* [[/Arrays/]]<br />
* [[/Strings/]]<br />
* [[/Integers/]]<br />
* [[/IO | I/O ]]<br />
* [[/Floating Point/]]<br />
* [[/Concurrency/]]<br />
* [[/Modules/]]<br />
* [[/Monads/]]<br />
<br />
== General techniques ==<br />
<br />
* [[/Strictness/]]<br />
* [[/Laziness/]]<br />
* [[/Space | Avoiding space leaks]]<br />
* [[/Accumulating parameter|Accumulating parameters]]<br />
* [[Stack_overflow|Avoiding stack overflow]]<br />
<br />
== Compiler specific techniques ==<br />
<br />
* [[/GHC/]]<br />
* [[/NHC98| nhc98]]<br />
* [[/Hugs/]]<br />
* [[/Yhc/]]<br />
* [[/JHC/]]<br />
<br />
== More information ==<br />
<br />
* There are plenty of good examples of Haskell code written for performance in the [http://shootout.alioth.debian.org/ The Computer Language Shootout Benchmarks]<br />
* And many alternatives, with discussion, on the [http://haskell.org/hawiki/ShootoutEntry old Haskell wiki]<br />
<br />
== Specific comparisons of data structures <br />
* Data.Sequence VS lists<br />
<br />
<haskell><br />
import Data.Sequence<br />
<br />
insert_million 0 sequence = sequence<br />
insert_million n sequence = insert_million (n - 1)(sequence |> n)<br />
<br />
main = putStrLn (show (Data.Sequence.length (insert_million 1000000 empty)))<br />
<br />
</haskell><br />
ghc -O2 --make InsertMillionElements.hs<br />
time ./InsertMillionElements +RTS -K100M <br />
<br />
1000000<br />
<br />
real 0m7.238s<br />
<br />
user 0m6.804s<br />
<br />
sys 0m0.228s<br />
<br />
<haskell><br />
insert_million 0 list = reverse list<br />
insert_million n list = insert_million (n -1) (n:list)<br />
<br />
main = putStrLn (show (length (insert_million 1000000 [])))<br />
</haskell> <br />
<br />
ghc -O2 --make InsertMillionElements.hs<br />
time ./InsertMillionElementsList +RTS -K100M <br />
<br />
1000000<br />
<br />
real 0m0.588s<br />
<br />
user 0m0.528s<br />
<br />
sys 0m0.052s<br />
<br />
Lists are substantially faster on this micro-benchmark. <br />
<br />
[[Category:Idioms]]<br />
[[Category:Language]]<br />
[[Category:Performance|*]]</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Performance/Monads&diff=14623Performance/Monads2007-07-24T01:05:29Z<p>Mnislaih: </p>
<hr />
<div>{{Performance infobox}}<br />
[[Category:Performance|Monads]]<br />
== Unroll your MTL stacks ==<br />
<br />
MTL is an excellent for programming with monads, however stacked monad transformers do not inline well and often impose a performance hit of up to 3X. <br />
<br />
If you care about this, the best option is to flatten you stack of transformers into a single, hand unrolled monad. An extreme example follows.<br />
<br />
This is a typical MTL monad stack<br />
<br />
newtype DRM a = DRM {unDRM:: ErrorT Finish (RWS () DNA RNA) a}<br />
deriving (MonadState DNA, MonadWriter RNA, MonadError Finish, Monad)<br />
<br />
We can unroll it as follows:<br />
<br />
<haskell><br />
type DRM = DRMonad<br />
newtype DRMonad a = DRMonad {runDRMonad :: DNA -> (Either Finish a,DNA,RNA)}<br />
<br />
instance Monad DRMonad where<br />
return x = DRMonad(\s -> (Right x, s, mempty))<br />
(>>= = bindDRMonad<br />
fail _ = DRMonad (\s->(Left Finish,s,mempty))<br />
<br />
{-# INLINE bindDRMonad #-}<br />
{-# INLINE bindDRMonad2 #-}<br />
bindDRMonad :: DRMonad a -> (a -> DRMonad b) -> DRMonad b<br />
bindDRMonad m f = DRMonad$ \s -> case runDRMonad m s of<br />
(x',s',w) -><br />
bindDRMonad2 x' (s',w,f)<br />
bindDRMonad2 x' (s',w, f) = case x' of <br />
Left e -> (Left e, s', w)<br />
Right r -> case runDRMonad (f r) s' of<br />
(x'',s'',w') -><br />
(x'', s'', w `mappend` w')<br />
</haskell></div>Mnislaihhttps://wiki.haskell.org/index.php?title=ICFP_Programming_Contest/Teams_2007&diff=14569ICFP Programming Contest/Teams 20072007-07-21T07:18:23Z<p>Mnislaih: </p>
<hr />
<div>This page is for helping Haskell (and FP) people organise teams for the<br />
[http://www.icfpcontest.org// 2007 ICFP contest].<br />
<br />
* [http://www.kingsrook.com/icfp/countdown.html Countdown to contest start]<br />
<br />
Resources:<br />
* The home of [http://www.icfpcontest.org/ ICFP 2007].<br />
* The #haskell-icfp07 and #haskell [[IRC channel]]s on freenode.<br />
* The #oasis [[IRC channel]] on freenode: generic ICFP discussion channel (not specifically Haskell oriented)<br />
* [http://article.gmane.org/gmane.comp.lang.haskell.cafe/24773 Announcement] for this page.<br />
<br />
== Teams ==<br />
<br />
Teams that are completed, and will be entering:<br />
<br />
{| border="0" cellspacing="15" cellpadding="2"<br />
! Team<br />
! Members<br />
|-<br />
| Lazy Bottoms<br />
| vincenz, Adept, Lemmih, psykotic, zeeeee, jethr0, Cale<br />
|-<br />
| The Church of the Least Fixed Point<br />
| desp, dreamer_, lispozord, q, rraptorr, tilk<br />
|-<br />
| Pointless<br />
| nominolo, Igloo, mauke<br />
|-<br />
| TNT <team named thunk><br />
| timbod, mnislaih, Toxaris<br />
|-<br />
| NITWIT (Not intending to Win It)<br />
| jfredett @ #haskell, Joeyfredette on AIM.<br />
|-<br />
| Instant Chaos <br />
| alar @ #haskell, #oasis, #haskell_ru , nealar @livejournal.com<br />
|-<br />
| Team PDX<br />
| Binkley et al<br />
|-<br />
| augustss<br />
| Lennart<br />
|-<br />
|}<br />
<br />
{| border="0" cellspacing="15" cellpadding="2"<br />
! Teams that sound like they use Haskell<br />
! Members<br />
|-<br />
| Poor Man's Haskell (maybe)<br />
| ?<br />
|-<br />
| PurelyFunctionalInfrastructure (maybe)<br />
| ?<br />
|-<br />
| Side Effects May Include... (maybe)<br />
| ?<br />
|-<br />
|}<br />
<br />
== Interested in competing ==<br />
<br />
Interested in competing, but need a team? Add your name and how to<br />
contact you here, and '''start contacting people on #haskell, and this<br />
list, to organise your team!'''<br />
<br />
{| border="0"<br />
! Name<br />
! Location<br />
! Skills<br />
! Contact<br />
|-<br />
| ''Lambdabot''<br />
| ''Sydney''<br />
| ''Looking up documentation''<br />
| ''#haskell''<br />
|-<br />
| ilyats<br />
| Israel<br />
| Math, Haskell98<br />
| eilya497 at 013.net<br />
|-<br />
| Andrew Wagner<br />
| US (EST time zone)<br />
| Math modelling, AI<br />
| chessguy on #haskell or wagner dot andrew _at_ gmail<br />
|-<br />
| Tim Chevalier <br />
| Portland, OR<br />
| Um... besides Haskell?<br />
| catamorphism@gmail.com / catamorphism on AIM / Binkley on #haskell<br />
|-<br />
| Arthur van Leeuwen<br />
| Utrecht, The Netherlands<br />
| parsing, language design<br />
| earthy on #haskell, #haskell.dut<br />
|-<br />
| Diego Navarro<br />
| Brazil<br />
| random bits of formal logic, statistics (LOTS of it, graduate-level), some random knowledge of Bird-Merteens Formalism. Oh, and economics, I'm actually an economist<br />
| quemseatreve at gmail dot com, syntaxfree on #haskell (most often on #haskell-blah, ab_gen@hotmail.com on MSN <br />
|-<br />
| Ivan Tarasov<br />
| St.Petersburg, Russia<br />
| Math, Haskell, some D, Ruby, some boring languages (Java, C, C++)<br />
| Ivan.Tarasov at gmail com, ivant on #haskell (sporadically), JabberID: tarasov@jabber.ru<br />
|}<br />
<br />
== How to contact people ==<br />
<br />
If possible, mention your nick on #haskell @ freenode.org, or #haskell-icfp07 @ freenode.org, then you'll be much easier to find.<br />
<br />
<br />
<br />
<br />
[[Category:Contest]]</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Hac_2007_II&diff=14132Hac 2007 II2007-07-10T07:22:21Z<p>Mnislaih: added myself</p>
<hr />
<div>[[Image:Hac-axe-icon.png|Hac icon]]<br />
<br />
Please add yourself to this list if you are potentially interested in<br />
being part of a Hackathon colocated with<br />
[http://www.cse.unsw.edu.au/~keller/haskellws/HaskellWorkshop.html Haskell Workshop] and<br />
[http://www.informatik.uni-bonn.de/~ralf/icfp07.html ICFP] 2007 (i.e. in<br />
Freiburg, Germany, around the end of September/beginning of October).<br />
<br />
* Ian Lynagh (Igloo)<br />
* Duncan Coutts (dcoutts)<br />
* Malcolm Wallace (malcolmw)<br />
* Don Stewart (dons)<br />
* Lennart Kolmodin (kolmodin)<br />
* Pepe Iborra (mnislaih)<br />
<br />
In terms of dates, IFL immediately preceedes HW, which immediately<br />
preceeds ICFP, so the best might be to go for the weekend Fri-Sun<br />
afterwards. This gives a days rest after a week's conferences, or CUFP<br />
for the diehards, on the Thursday.<br />
<br />
An alternative might be to run the Hackathon in parallel with IFL (or<br />
ICFP), but this might result in some people who want to go not being<br />
able to make much of it.<br />
<br />
== Potential topics for a group hack ==<br />
<br />
Add ideas here for which you think hacking together as a group (rather than individually) would be beneficial.<br />
<br />
* bytestring 1.0<br />
* bit layer on Data.Binary 1.0<br />
* Data.ByteString.Parallel<br />
* Lots of Cabal hacking still to be done<br />
* Bindings for <your favourite C library><br />
* Haskell library for <your favourite task><br />
<br />
== Previous Haskell hackathons ==<br />
<br />
* [[Hac_2007|Hac 2007 - Oxford]]<br />
* [http://hackage.haskell.org/trac/ghc/wiki/Hackathon Hac 2006 - Portland]<br />
<br />
[[Category:Community]]</div>Mnislaihhttps://wiki.haskell.org/index.php?title=ICFP_Programming_Contest/Teams_2007&diff=14089ICFP Programming Contest/Teams 20072007-07-09T08:38:51Z<p>Mnislaih: got a team</p>
<hr />
<div>This page is for helping Haskell (and FP) people organise teams for the<br />
[http://www.icfpcontest.org// 2007 ICFP contest].<br />
<br />
* [http://www.kingsrook.com/icfp/countdown.html Countdown to contest start]<br />
<br />
Resources:<br />
* The home of [http://www.icfpcontest.org/ ICFP 2007].<br />
* The #haskell-icfp07 and #haskell [[IRC channel]]s on freenode.<br />
* [http://article.gmane.org/gmane.comp.lang.haskell.cafe/24773 Announcement] for this page.<br />
<br />
== Teams ==<br />
<br />
Teams that are completed, and will be entering:<br />
<br />
{| border="0" cellspacing="0" cellpadding="2"<br />
! Team<br />
! Members<br />
|-<br />
| Lazy Bottoms<br />
| vincenz, Adept, Lemmih, psykotic, zeeeeee, jethr0, Cale<br />
|}<br />
<br />
== Teams seeking players ==<br />
<br />
Are you organising a team, and need more players? Add your team and<br />
contact details here:<br />
<br />
{| border="0" cellspacing="0" cellpadding="2"<br />
! Team<br />
! Current members<br />
! Number required<br />
! Contact<br />
|-<br />
| ''CoolHackers''<br />
| ''0''<br />
| ''0''<br />
| ''lambdabot @ #haskell''<br />
|-<br />
| FieryNewbz<br />
| 3<br />
| 5<br />
| syntaxfree @ #haskell<br />
|-<br />
| TNT <team named thunk><br />
| 3<br />
| 5<br />
| timbod @ #haskell, twd_gg AT dockerz DOT net<br />
|}<br />
<br />
== Interested in competing ==<br />
<br />
Interested in competing, but need a team? Add your name and how to<br />
contact you here, and '''start contacting people on #haskell, and this<br />
list, to organise your team!'''<br />
<br />
{| border="0"<br />
! Name<br />
! Location<br />
! Skills<br />
! Contact<br />
|-<br />
| ''Lambdabot''<br />
| ''Sydney''<br />
| ''Looking up documentation''<br />
| ''#haskell''<br />
|-<br />
| jfredett (Joe Fredette)<br />
| Bellingham, MA, US of A<br />
| Math, Math, and more Math, Scheme too.<br />
| AIM: Joeyfredette / #haskell<br />
|-<br />
| ilyats<br />
| Israel<br />
| Math, Haskell98<br />
| eilya497 at 013.net<br />
|-<br />
| Andrew Wagner<br />
| US (EST time zone)<br />
| Math modelling, AI<br />
| chessguy on #haskell or wagner dot andrew _at_ gmail<br />
|-<br />
| desp (Mietek Bak)<br />
| Poland<br />
| Not afraid of dirty C/C++ work<br />
| mietek@gmail.com / #haskell<br />
|-<br />
| Tim Chevalier <br />
| Portland, OR<br />
| Um... besides Haskell?<br />
| catamorphism@gmail.com / catamorphism on AIM / Binkley on #haskell<br />
|-<br />
| Tim Docker<br />
| Sydney<br />
| graphics, visualisation, distributed processing<br />
| timbod on #haskell (sporadically), or twd_gg AT dockerz DOT net<br />
|-<br />
| Tillmann Rendel<br />
| Germany<br />
| programming, logic<br />
| rendel at rbg dot informatik dot tu-darmstadt dot de, Toxaris on #haskell<br />
|-<br />
| Arthur van Leeuwen<br />
| Utrecht, The Netherlands<br />
| parsing, language design<br />
| earthy on #haskell, #haskell.dut<br />
|-<br />
| Diego Navarro<br />
| Brazil<br />
| random bits of formal logic, statistics (LOTS of it, graduate-level), some random knowledge of Bird-Merteens Formalism. Oh, and economics, I'm actually an economist<br />
| quemseatreve at gmail dot com, syntaxfree on #haskell (most often on #haskell-blah, ab_gen@hotmail.com on MSN <br />
|}<br />
<br />
== How to contact people ==<br />
<br />
If possible, mention your nick on #haskell @ freenode.org, or #haskell-icfp07 @ freenode.org, then you'll be much easier to find.<br />
<br />
[[Category:Contest]]</div>Mnislaihhttps://wiki.haskell.org/index.php?title=ICFP_Programming_Contest/Teams_2007&diff=13890ICFP Programming Contest/Teams 20072007-06-30T08:40:22Z<p>Mnislaih: me looking for a team</p>
<hr />
<div>This page is for helping Haskell (and FP) people organise teams for the<br />
[http://www.icfpcontest.org// 2007 ICFP contest].<br />
<br />
* [http://www.kingsrook.com/icfp/countdown.html Countdown to contest start]<br />
<br />
Resources:<br />
* The home of [http://www.icfpcontest.org/ ICFP 2007].<br />
* The #haskell-icfp07 and #haskell [[IRC channel]]s on freenode.<br />
* [http://article.gmane.org/gmane.comp.lang.haskell.cafe/24773 Announcement] for this page.<br />
<br />
== Full teams ==<br />
<br />
Teams that are completed, and will be entering:<br />
<br />
{| border="0" cellspacing="0" cellpadding="2"<br />
! Team<br />
! Members<br />
|-<br />
|}<br />
<br />
<br />
== Teams seeking players ==<br />
<br />
Are you organising a team, and need more players? Add your team and<br />
contact details here:<br />
<br />
{| border="0" cellspacing="0" cellpadding="2"<br />
! Team<br />
! Current members<br />
! Number required<br />
! Contact<br />
|-<br />
| ''CoolHackers''<br />
| ''0''<br />
| ''0''<br />
| ''lambdabot @ #haskell''<br />
|}<br />
<br />
== Interested in competing ==<br />
<br />
Interested in competing, but need a team? Add your name and how to<br />
contact you here:<br />
<br />
{| border="0"<br />
! Name<br />
! Location<br />
! Skills<br />
! Contact<br />
|-<br />
| ''Lambdabot''<br />
| ''Sydney''<br />
| ''Looking up documentation''<br />
| ''#haskell''<br />
|-<br />
| jfredett (Joe Fredette)<br />
| Bellingham, MA, US of A<br />
| Math, Math, and more Math<br />
| AIM: Joeyfredette<br />
|-<br />
| mnislaih<br />
| Spain<br />
| none. sleeps less than most peeps<br />
| mnislaih@gmail.com / #haskell<br />
|-<br />
|}<br />
<br />
<br />
[[Category:Contest]]</div>Mnislaihhttps://wiki.haskell.org/index.php?title=GHC/GHCi_debugger&diff=13744GHC/GHCi debugger2007-06-26T15:27:43Z<p>Mnislaih: Remove a lot of out-of-date stuff to avoid confusion.</p>
<hr />
<div>[[Category:GHC|GHCi debugger]]<br />
The GHCi Debugger project extends ghci with basic debugging capabilities. See the GHC user docs for more info.<br />
<br />
== Current status == <br />
The debugger is currently available in GHC 6.7 [http://haskell.org/ghc/dist/current/dist nightly builds], and is reasonably stable: grab a HEAD snapshot and play with it. Full documentation in the [http://www.haskell.org/ghc/dist/current/docs/ HEAD user docs].</div>Mnislaihhttps://wiki.haskell.org/index.php?title=GHC/GHCi_debugger&diff=13743GHC/GHCi debugger2007-06-26T15:23:36Z<p>Mnislaih: </p>
<hr />
<div>[[Category:GHC|GHCi debugger]]<br />
The GHCi Debugger project extends ghci with basic debugging capabilities. The GHC 6.7 documentation includes a section on the debugger. <br />
<br />
This page is a dump of the designs, ideas, and results of the project. Check [http://darcs.haskell.org/SoC/ghc.debugger/demo.mov here] for a Quicktime video demonstrating the use of the debugger.<br />
<br />
== Current status == <br />
UPDATE: The debugger is currently available in GHC 6.7 [http://haskell.org/ghc/dist/current/dist nightly builds], so there is no excuse anymore: grab a HEAD snapshot and play with it. Full documentation in the [http://www.haskell.org/ghc/dist/current/docs/ HEAD user docs]. <br />
<br />
=== Feature wise ===<br />
* Stack Traces have been dropped and are not being pursued at the moment<br />
* The Closure viewer includes support for everything in GHC, but currently GADTs might be problematic<br />
* Dynamic breakpoints are fully supported<br />
<br />
== Intermediate closure viewer ==<br />
The closure viewer is intended to permit working with polymorphic values in breakpoints, as well as to explore intermediate computations without altering the evaluation order.<br />
<br />
This feature is now (more or less) complete. Currently it provides two new commands under ghci, ''':print''' and ''':sprint''', both used in the same way as <tt>:type</tt> or <tt>:info</tt>. The latter prints a semievaluated closure using underscores to represent suspended computations (pretty much as [[Hood]] does). The former one in addition binds these thunks to variable names, so that you can do things with them.<br />
<br />
Example:<br />
<pre><br />
Prelude> let li = map Just [1..5]<br />
Prelude> length li<br />
5<br />
Prelude> :sp li<br />
li - [_,_,_,_,_,]<br />
<br />
Prelude> head li<br />
Just 1<br />
<br />
Prelude> :sp li<br />
li - [Just 1,_,_,_,_]<br />
<br />
Prelude> last li<br />
Just 5<br />
<br />
Prelude> :sp li<br />
li - [Just 1,_,_,_Just 5]<br />
<br />
Prelude> :p li<br />
li - [Just 1, (_t1::Maybe Integer),(_t2::Maybe Integer),(_t3::Maybe Integer),Just 5]<br />
<br />
Prelude> _t1 `seq` ()<br />
<br />
Prelude> :p li<br />
li - [Just 1, Just 2,(_t3::Maybe Integer),(_t4::Maybe Integer),Just 5]<br />
<br />
Prelude> _t2<br />
Just 3<br />
</pre><br />
<br />
Its best feature is that it can work without type information, so you can display polymorphic objects the type of which you don't know. However if there is type information available, it is used. Thanks to this it can work with opaque or coerced types. For instance:<br />
<br />
<haskell><br />
data Opaque = forall a. O a<br />
</haskell><br />
<br />
<pre><br />
*Test2> let li = map Just [1..5]<br />
*Test2> let o = O li<br />
*Test2> head li `seq` ()<br />
*Test2> length li `seq` ()<br />
*Test2> :p o<br />
o - [O Just 1,(_t1::Integer),(_t2::Integer),(_t3::Integer),(_t4::Integer)]<br />
</pre><br />
<br />
In the example above the <tt>li</tt> inside <tt>o</tt> has an opaque existential type. However, the closure viewer makes it possible to recover its type when it gets evaluated.<br />
<br />
Other currently proposed extensions are a <tt>safeCoerce</tt> function (not so useful, it depends on ghc-api) and an <tt>unsafeDeepSeq</tt> (this one is decoupled from ghc-api). There is also a generally useful (for compiler/tool developers) <tt>isFullyEvaluated</tt> query function. The signatures being:<br />
<br />
<pre><br />
isFullyEvaluated :: a -> IO Bool <br />
unsafeDeepSeq :: a -> b -> b <br />
safeCoerce :: GHC.Session -> a -> Maybe b<br />
</pre><br />
<br />
Finally, note that there are some inconveniences with the current implementation, such as <tt>:p</tt> binding the same closure to different names when used twice on the same closure, but they are minor and temporary (hopefully). <br />
<br />
== Dynamic breakpoints ==<br />
<br />
See the user details of the current implementation at the GHC User Guide. <br />
<br />
=== Event sites and events ===<br />
We define 'event sites' as points in the code where you can want to set a breakpoint. Current candidates for sites are:<br />
* On the entrance to a function / lambda abstraction<br />
* <strike>Prior to function applications</strike> ''(this one does not make sense unless it forces the application using <tt>$!</tt>)<br />
* Local bindings in lets and wheres<br />
* Entrance to statements in monadic-do code<br />
<br />
Overlapping or unnecesary events should be coalesced into a single one. <br />
The rationale for what is an event and what is not is trying to find a middle point between the user interests and the overhead introduced:<br />
* We want to keep the overhead manageable, thus we want to keep the number of breakpoints low.<br />
* The user wants to introduce breakpoints at will.<br />
<br />
Credit goes to both A. Tolmach's ML debugger and the OCaml time-travel debugger for providing the inspiration.<br />
<br />
=== Proposals ===<br />
There are currently the following proposals:<br />
<br />
* Instrument the code with a conditional breakpoint at every event site. Sites are numbered, and the condition uses a site-indexed array to check if there is a breakpoint enabled. The array is maintained inside ghci. Hopefully not much magic is required for this one.<br />
<br />
* In the style of the previous one, but no array is maintained. All the breakpoint conditions are set to False, so almost no overhead is incurred. When the user demands a breakpoint, its BCO in the heap is rewritten to enable the breakpoint. Feasibility of this?<br />
<br />
* Don't use instrumentation. Have a new header for BCOs with breakpoints, say BCO_BREAK, and change headers in execution time on user demand (as in the previous proposal). The problem I see with this one is how to extract the local bindings. I don't fully grok the scheme Lemmih uses to do that yet.<br />
<br />
During this project we have explored the first one, under the lemma of ``do the simplest thing that could possibly work``. <br />
I'm sure there are many other designs. Please add your proposal or just throw an idea in.<br />
<br />
== Call traces ==<br />
We want to have ''strict'' call traces, not the lazy ones. <br />
<br />
=== Proposals ===<br />
<br />
* It has been suggested that stealing ideas from Cost-Centre Stacks may be useful. <br />
<br />
<strike><br />
* Based on Tolmach's debugger, we can instrument the source code to build a timeline of events (either lazily or not). The events contain a pointer to its lexical parent event. With that it should be possible to extract a call trace:<br />
# CASE 1: We are in a Function definition (FN):<br />
## Go back one step in the timeline: it necessarily is an application (APP)<br />
## Go back to its 'binding', i.e. its lexical parent. Keep doing this until it is a FN, then start again from case 1.<br />
## Once you reach the top, i.e. the 0 event, you are done. Display all theAPPs you encountered in the way<br />
# CASE 2: We are in a site other than a FN:<br />
## Go back [[lexically]] until you hit a FN and continue with case 1.<br />
<br />
This is just a wild, untested idea. It's possible that it would not work. Also even if it worked, it's possible that the overhead was unadmissible.<br />
</strike> WON'T WORK WITH LAZINESS<br />
<br />
== Integration ==<br />
Allowing other tools to integrate with the debugger is an important goal. It should not be taken lightly though.<br />
<br />
* It has been suggested to create a client/server protocol so that the debugger can be used by other tools.<br />
<br />
* On the other hand, arguably it would be much easier to provide integration to clients of the ghc-api via some form of debugger api.<br />
<br />
* Finally, it should be possible to derive the client/server architecture as an afterthought provided there is a debugger api in the ghc-api.<br />
<br />
== Further pointers ==<br />
<br />
# [http://www.tekno.chalmers.se/~murk/rectus Rectus], '' Oleg M&uuml;rk and Lennart Kolmodin''<br />
# [http://caml.inria.fr/pub/docs/manual-ocaml/manual030.html The Ocaml Debugger], ''The OCaml Team''<br />
# [http://web.cecs.pdx.edu/~apt/jfp95.ps A debugger for Standard ML], ''A.Tolmach, A. Appel''<br />
# [http://www.haskell.org//pipermail/cvs-ghc/2006-April/029040.html The original discussion in the ghc-cvs mailing list]<br />
<br />
== How to get the patches ==<br />
<br />
The patches are available at the SoC ghc.debugger [http://darcs.haskell.org/SoC/ghc.debugger/ darcs repo]:<br />
<pre><br />
darcs get --partial http://darcs.haskell.org/SoC/ghc.debugger<br />
</pre><br />
This is a modified version of GHC 6.6. Build it following the instructions at the [http://hackage.haskell.org/trac/ghc GHC developers wiki].<br />
<br />
If darcs-all does not do it for you, you will need to manually pull a few patches at the libraries/base repo, to be pulled from http://darcs.haskell.org/SoC/ghc.debugger/libraries/base<br />
<br />
Have fun! (and feel free to spam [mailto:mnislaih@gmail.com me] with bugs, suggestions or requests!)</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Talk:The_Monad.Reader&diff=10979Talk:The Monad.Reader2007-02-03T13:50:57Z<p>Mnislaih: </p>
<hr />
<div>I'd welcome any feedback and discussion about The Monad.Reader. Don't like the class file? Love the articles? Shout it out!<br />
--[[User:WouterSwierstra|WouterSwierstra]] 10:38, 31 January 2007 (UTC)<br />
<br />
<br />
== The layout ==<br />
<br />
I think the <tt>twosided</tt> should be dropped from the latex class file, that would make it a lot more pleasant to read on a screen.<br />
<br />
--[[User:Twanvl|Twanvl]] 13:50, 31 January 2007 (UTC)<br />
<br />
Although those of use with wide screens quite like putting the pdf up in 2-page side-by-side mode in which the twosided option looks better!<br />
<br />
--[[User:Pharm|Pharm]] 11:26, 1 February 2007 (UTC) (I have an ordinary 4:3 screen at home though. TBH the twosided thing doesn't bother me either way...)<br />
<br />
--[[User:Mnislaih|Mnislaih]] 13:50, 3 February 2007 (UTC)<br />
Wow! This issue of TMR is excellent. I am loving the tutorial style of all the three articles. Right now I'm in section 2 of Russell's excellent assembler and found that the newtype definition for the AssemblyCodeMonad needs to be:<br />
<haskell><br />
newtype AssemblyCodeMonad a = <br />
AssemblyCodeMonad<br />
(RWS [(Label,Location)]<br />
[Either (Instruction Register) (Label,Location)]<br />
(Location, Integer)<br />
a)<br />
deriving (Monad, MonadReader [(Label,Location)], <br />
MonadWriter [Either (Instruction Register) (Label,Location)],<br />
MonadState (Location, Integer))<br />
</haskell></div>Mnislaihhttps://wiki.haskell.org/index.php?title=Hac_2007/GroupPhoto&diff=10127Hac 2007/GroupPhoto2007-01-12T14:27:34Z<p>Mnislaih: </p>
<hr />
<div>[[Image:Hac2007-group-outside.jpg]]<br />
<br />
Hac2007 peoples standing outside the Oxford university computing lab.<br />
11th Jan 2007.<br />
<br />
----<br />
<br />
'''Top Row'''<br />
<br />
From left: Thorkil Naur, Neil Mitchell (ndm), Ketil Malde, David Waern, Dominic Steinitz, Simon Marlow (JaffaCake), Ben Lippmeier (benl23)<br />
<br />
<br />
'''Middle Row'''<br />
<br />
From left: Benedikt Schmidt (beschmi), Pepe Iborra (mnislaih)<br />
<br />
'''Bottom Row'''<br />
<br />
From left: Ian Lynagh (Igloo), Duncan Coutts (dcoutts), Bjorn Bringert (bringert), Don Stewart (dons), Kirsten Chevalier (Binkley), Lennart Kolmodin (kolmodin), David Himmelstrup (Lemmih).<br />
<br />
<br />
== Summary ==<br />
<br />
dons: Worked on the new [http://darcs.haskell.org/binary binary] IO package,<br />
and patched hmp3 and lambdabot to use the new package. Lambdabot's now<br />
running live with 'binary' state<br />
<br />
Binkley: Worked on [http://hackage.haskell.org/trac/ghc/wiki/Commentary/Profiling ticky-ticky profiling in GHC]. Pending review, that code is ready to go into GHC's HEAD.<br />
<br />
pepe: Produced some GHC patches related to the [http://www.haskell.org/ghc/dist/current/docs/users_guide/ghci-debugger.html GHCi debugger], and joined<br />
forces with beschmi to integrate the debugger in Emacs, building on top of beschmi<br />
code to use the ghc-api from Emacs. A new project sponsored by Hac'07 !</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Hac_2007/GroupPhoto&diff=10126Hac 2007/GroupPhoto2007-01-12T14:26:32Z<p>Mnislaih: </p>
<hr />
<div>[[Image:Hac2007-group-outside.jpg]]<br />
<br />
Hac2007 peoples standing outside the Oxford university computing lab.<br />
11th Jan 2007.<br />
<br />
----<br />
<br />
'''Top Row'''<br />
<br />
From left: Thorkil Naur, Neil Mitchell (ndm), Ketil Malde, David Waern, Dominic Steinitz, Simon Marlow (JaffaCake), Ben Lippmeier (benl23)<br />
<br />
<br />
'''Middle Row'''<br />
<br />
From left: Benedikt Schmidt (beschmi), Pepe Iborra (mnislaih)<br />
<br />
'''Bottom Row'''<br />
<br />
From left: Ian Lynagh (Igloo), Duncan Coutts (dcoutts), Bjorn Bringert (bringert), Don Stewart (dons), Kirsten Chevalier (Binkley), Lennart Kolmodin (kolmodin), David Himmelstrup (Lemmih).<br />
<br />
<br />
== Summary ==<br />
<br />
dons: Worked on the new [http://darcs.haskell.org/binary binary] IO package,<br />
and patched hmp3 and lambdabot to use the new package. Lambdabot's now<br />
running live with 'binary' state<br />
<br />
Binkley: Worked on [http://hackage.haskell.org/trac/ghc/wiki/Commentary/Profiling ticky-ticky profiling in GHC]. Pending review, that code is ready to go into GHC's HEAD.<br />
<br />
pepe: Produced some GHC patches related to the GHCi debugger, and joined<br />
forces with beschmi to integrate the debugger in Emacs, building on top of beschmi<br />
code to use the ghc-api from Emacs. A new project sponsored by Hac'07 !</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Hac_2007/GroupPhoto&diff=10122Hac 2007/GroupPhoto2007-01-12T12:17:58Z<p>Mnislaih: </p>
<hr />
<div>[[Image:Hac2007-group-outside.jpg]]<br />
<br />
Hac2007 peoples standing outside the Oxford university computing lab.<br />
11th Jan 2007.<br />
<br />
----<br />
<br />
'''Top Row'''<br />
<br />
From left: Thorkil Naur, Neil Mitchell (ndm), Ketil Malde, David Waern, Dominic Steinitz, Simon Marlow (JaffaCake), Ben Lippmeier (benl23)<br />
<br />
<br />
'''Middle Row'''<br />
<br />
From left: Benedikt Schmidt (beschmi), Pepe Iborra (mnislaih)<br />
<br />
'''Bottom Row'''<br />
<br />
From left: Ian Lynagh (Igloo), Duncan Coutts (dcoutts), Bjorn Bringert (bringert), Don Stewart (dons), Kirsten Chevalier (Binkley), Lennart Kolmodin (kolmodin), David Himmelstrup (Lemmih).</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Hac_2007/Projects&diff=9978Hac 2007/Projects2007-01-09T08:25:16Z<p>Mnislaih: </p>
<hr />
<div>* Darcs<br />
* GHC<br />
* libraries bugs<br />
* integrating SoC code<br />
* new releases <br />
* AJAX/HAppS?<br />
* Yhc + Cabal + Base<br />
* Haskell installer project, Gtk2Hs/GHC/Hugs/Cabal unified installer for Windows<br />
* Gtk2Hs + Gtk + GHC + Windows + Threads<br />
<br />
* porting libraries<br />
* new library/tool releases<br />
* compiler ports: want to get YHC running on your favourite machine?<br />
* new tools<br />
* infrastructure hacking: cabal, hackage<br />
* documentation<br />
* tutorials<br />
* bug squashing<br />
* feature implementations (walk the Trac list)<br />
* External core (Yhc and GHC): Making the (Haskell) external core interpreter in ghc/utils/ext-core work (again?)<br />
* A suitable low overhead GHC (+ others?) run time system interface to Integer C functions<br />
* http://hackage.haskell.org/trac/ghc/ticket/595 (Overhaul GHC's overlapping/non-exhaustive pattern checking)<br />
* Mac OS X test failures (ghc-6.6 and ghc-HEAD)<br />
* GHCi debugger: integrate in Emacs and/or Visual Haskell</div>Mnislaihhttps://wiki.haskell.org/index.php?title=GHC/GHCi_debugger&diff=9843GHC/GHCi debugger2006-12-31T13:15:49Z<p>Mnislaih: The patches are now in GHC 6.7</p>
<hr />
<div>The GHCi Debugger project extends ghci with basic debugging capabilities. The GHC 6.7 [http://haskell.org/ghc/dist/current/dist/docs documentation] includes a section on the debugger. <br />
<br />
This page is a dump of the designs, ideas, and results of the project. Check [http://darcs.haskell.org/SoC/ghc.debugger/demo.mov here] for a Quicktime video demonstrating the use of the debugger.<br />
<br />
== Current Status == <br />
UPDATE: The debugger is currently available in GHC 6.7 [http://haskell.org/ghc/dist/current/dist nightly builds], so there is no excuse anymore. <br />
GHC 6.8 will probably include a debugger, which may or may not be based on this one. <br />
<br />
=== Feature Wise ===<br />
* Stack Traces have been dropped and are not being pursued at the moment<br />
* The Closure viewer includes support for everything in GHC, but currently GADTs might be problematic<br />
* Dynamic breakpoints are fully supported<br />
<br />
== Intermediate Closure Viewer ==<br />
The closure viewer is intended to permit working with polymorphic values in breakpoints, as well as to explore intermediate computations without altering the evaluation order.<br />
<br />
This feature is now (more or less) complete. Currently it provides two new commands under ghci, ''':print''' and ''':sprint''', both used in the same way as <tt>:type</tt> or <tt>:info</tt>. The latter prints a semievaluated closure using underscores to represent suspended computations (pretty much as [[Hood]] does). The former one in addition binds these thunks to variable names, so that you can do things with them.<br />
<br />
Example:<br />
<pre><br />
Prelude> let li = map Just [1..5]<br />
Prelude> length li<br />
5<br />
Prelude> :sp li<br />
li - [_,_,_,_,_,]<br />
<br />
Prelude> head li<br />
Just 1<br />
<br />
Prelude> :sp li<br />
li - [Just 1,_,_,_,_]<br />
<br />
Prelude> last li<br />
Just 5<br />
<br />
Prelude> :sp li<br />
li - [Just 1,_,_,_Just 5]<br />
<br />
Prelude> :p li<br />
li - [Just 1, (_t1::Maybe Integer),(_t2::Maybe Integer),(_t3::Maybe Integer),Just 5]<br />
<br />
Prelude> _t1 `seq` ()<br />
<br />
Prelude> :p li<br />
li - [Just 1, Just 2,(_t3::Maybe Integer),(_t4::Maybe Integer),Just 5]<br />
<br />
Prelude> _t2<br />
Just 3<br />
</pre><br />
<br />
Its best feature is that it can work without type information, so you can display polymorphic objects the type of which you don't know. However if there is type information available, it is used. Thanks to this it can work with opaque or coerced types. For instance:<br />
<br />
<haskell><br />
data Opaque = forall a. O a<br />
</haskell><br />
<br />
<pre><br />
*Test2> let li = map Just [1..5]<br />
*Test2> let o = O li<br />
*Test2> head li `seq` ()<br />
*Test2> length li `seq` ()<br />
*Test2> :p o<br />
o - [O Just 1,(_t1::Integer),(_t2::Integer),(_t3::Integer),(_t4::Integer)]<br />
</pre><br />
<br />
In the example above the <tt>li</tt> inside <tt>o</tt> has an opaque existential type. However, the closure viewer makes it possible to recover its type when it gets evaluated.<br />
<br />
Other currently proposed extensions are a <tt>safeCoerce</tt> function (not so useful, it depends on ghc-api) and an <tt>unsafeDeepSeq</tt> (this one is decoupled from ghc-api). There is also a generally useful (for compiler/tool developers) <tt>isFullyEvaluated</tt> query function. The signatures being:<br />
<br />
<pre><br />
isFullyEvaluated :: a -> IO Bool <br />
unsafeDeepSeq :: a -> b -> b <br />
safeCoerce :: GHC.Session -> a -> Maybe b<br />
</pre><br />
<br />
Finally, note that there are some inconveniences with the current implementation, such as <tt>:p</tt> binding the same closure to different names when used twice on the same closure, but they are minor and temporary (hopefully). <br />
<br />
== Dynamic Breakpoints ==<br />
<br />
See the user details of the current implementation at the GHC User Guide. <br />
<br />
=== Event sites and events ===<br />
We define 'event sites' as points in the code where you can want to set a breakpoint. Current candidates for sites are:<br />
* On the entrance to a function / lambda abstraction<br />
* <strike>Prior to function applications</strike> ''(this one does not make sense unless it forces the application using <tt>$!</tt>)<br />
* Local bindings in lets and wheres<br />
* Entrance to statements in monadic-do code<br />
<br />
Overlapping or unnecesary events should be coalesced into a single one. <br />
The rationale for what is an event and what is not is trying to find a middle point between the user interests and the overhead introduced:<br />
* We want to keep the overhead manageable, thus we want to keep the number of breakpoints low.<br />
* The user wants to introduce breakpoints at will.<br />
<br />
Credit goes to both A. Tolmach's ML debugger and the OCaml time-travel debugger for providing the inspiration.<br />
<br />
=== Proposals ===<br />
There are currently the following proposals:<br />
<br />
* Instrument the code with a conditional breakpoint at every event site. Sites are numbered, and the condition uses a site-indexed array to check if there is a breakpoint enabled. The array is maintained inside ghci. Hopefully not much magic is required for this one.<br />
<br />
* In the style of the previous one, but no array is maintained. All the breakpoint conditions are set to False, so almost no overhead is incurred. When the user demands a breakpoint, its BCO in the heap is rewritten to enable the breakpoint. Feasibility of this?<br />
<br />
* Don't use instrumentation. Have a new header for BCOs with breakpoints, say BCO_BREAK, and change headers in execution time on user demand (as in the previous proposal). The problem I see with this one is how to extract the local bindings. I don't fully grok the scheme Lemmih uses to do that yet.<br />
<br />
During this project we have explored the first one, under the lemma of ``do the simplest thing that could possibly work``. <br />
I'm sure there are many other designs. Please add your proposal or just throw an idea in.<br />
<br />
== Call Traces ==<br />
We want to have ''strict'' call traces, not the lazy ones. <br />
<br />
=== Proposals ===<br />
<br />
* It has been suggested that stealing ideas from Cost-Centre Stacks may be useful. <br />
<br />
<strike><br />
* Based on Tolmach's debugger, we can instrument the source code to build a timeline of events (either lazily or not). The events contain a pointer to its lexical parent event. With that it should be possible to extract a call trace:<br />
# CASE 1: We are in a Function definition (FN):<br />
## Go back one step in the timeline: it necessarily is an application (APP)<br />
## Go back to its 'binding', i.e. its lexical parent. Keep doing this until it is a FN, then start again from case 1.<br />
## Once you reach the top, i.e. the 0 event, you are done. Display all theAPPs you encountered in the way<br />
# CASE 2: We are in a site other than a FN:<br />
## Go back [[lexically]] until you hit a FN and continue with case 1.<br />
<br />
This is just a wild, untested idea. It's possible that it would not work. Also even if it worked, it's possible that the overhead was unadmissible.<br />
</strike> WON'T WORK WITH LAZINESS<br />
<br />
== Integration ==<br />
Allowing other tools to integrate with the debugger is an important goal. It should not be taken lightly though.<br />
<br />
* It has been suggested to create a client/server protocol so that the debugger can be used by other tools.<br />
<br />
* On the other hand, arguably it would be much easier to provide integration to clients of the ghc-api via some form of debugger api.<br />
<br />
* Finally, it should be possible to derive the client/server architecture as an afterthought provided there is a debugger api in the ghc-api.<br />
<br />
== Further pointers ==<br />
<br />
# [http://www.tekno.chalmers.se/~murk/rectus Rectus], '' Oleg M&uuml;rk and Lennart Kolmodin''<br />
# [http://caml.inria.fr/pub/docs/manual-ocaml/manual030.html The Ocaml Debugger], ''The OCaml Team''<br />
# [http://web.cecs.pdx.edu/~apt/jfp95.ps A debugger for Standard ML], ''A.Tolmach, A. Appel''<br />
# [http://www.haskell.org//pipermail/cvs-ghc/2006-April/029040.html The original discussion in the ghc-cvs mailing list]<br />
<br />
== How to get the patches ==<br />
<br />
The patches are available at the SoC ghc.debugger [http://darcs.haskell.org/SoC/ghc.debugger/ darcs repo]:<br />
<pre><br />
darcs get --partial http://darcs.haskell.org/SoC/ghc.debugger<br />
</pre><br />
This is a modified version of GHC 6.6. Build it following the instructions at the [http://hackage.haskell.org/trac/ghc GHC developers wiki].<br />
<br />
If darcs-all does not do it for you, you will need to manually pull a few patches at the libraries/base repo, to be pulled from http://darcs.haskell.org/SoC/ghc.debugger/libraries/base<br />
<br />
Have fun! (and feel free to spam [mailto:mnislaih@gmail.com me] with bugs, suggestions or requests!)</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Hac_2007/Attendees&diff=9570Hac 2007/Attendees2006-12-18T13:36:37Z<p>Mnislaih: Add accomodation plans</p>
<hr />
<div>[[Image:Hac-axe-icon.png|Hac icon]]<br />
<br />
Attendee list<br />
<br />
{|<br />
! Name<br />
! IRC nick<br />
! Dates<br />
! Projects<br />
|-<br />
| Don Stewart<br />
| dons<br />
| 10,11,12<br />
| Hackage, ByteStrings, stream fusion<br />
|-<br />
| Duncan Coutts<br />
| dcoutts<br />
| 10,11,12<br />
|<br />
|-<br />
| Ian Lynagh<br />
| Igloo<br />
| 10,11,12<br />
| GHC, Cabal, Hackage, and loads more besides<br />
|-<br />
| Neil Mitchell<br />
| ndm<br />
| 10,11,12<br />
| Yhc, Hoogle, Catch, Dr Haskell, WinHugs ...<br />
|-<br />
| Thorkil Naur<br />
| naur<br />
| 10,11,12<br />
| Integer implementation (GMP), Porting, Factorization, Puzzles<br />
|-<br />
| Pepe Iborra<br />
| mnislaih<br />
| 10,11,12<br />
| GHC, the GHCi debugger, Darcs does look sexy, infrastructure & tools.<br />
|-<br />
| Dominic Steinitz<br />
|<br />
| 10,11,12<br />
| crypto, networking<br />
|-<br />
| Ben Lippmeier<br />
| benl23<br />
| 10,11,12<br />
| GHC bug squashing.<br />
|-<br />
| David Himmelstrup<br />
| Lemmih<br />
| 10,11,12<br />
| cabal-test, QuickCheck, Hackage, cabal-get.<br />
|-<br />
| Ross Paterson<br />
|<br />
| ?<br />
| Hackage<br />
|-<br />
| Simon Marlow<br />
| JaffaCake<br />
| 1 or 2 days<br />
| Everything<br />
|- <br />
| Björn Bringert<br />
| bringert<br />
| 10,11,12<br />
| Hackage, libraries, QuickCheck 2, GHC<br />
|-<br />
| Benedikt Schmidt<br />
| beschmi<br />
| 10,11,12<br />
| darcs, GHC-api+Emacs, crypto<br />
|-<br />
| Krasimir Angelov<br />
| <br />
| 10,11,12<br />
| Visual Haskell, Cabal<br />
|-<br />
| Peter Nuttall<br />
| psnl<br />
| 10,11,12<br />
| Hat, maybe cabal or ghc<br />
|}<br />
<br />
<br />
<br />
== Arriving ==<br />
<br />
If you are arriving via air and want to meet up for the trip up to<br />
Oxford, add you details here, so people can arrange to travel together:<br />
<br />
{|<br />
|-<br />
! Name<br />
! Airport<br />
! Arrival date/time<br />
! Flight <br />
|-<br />
| dons<br />
| Heathrow<br />
| 2007-01-10 6:20am<br />
| QF31<br />
|-<br />
| bringert<br />
| Heathrow<br />
| 2007-01-10 8:25am<br />
| SK523<br />
|-<br />
| pepe<br />
| Stansted<br />
| 2007-01-09 6:10pm<br />
| 3840<br />
|-<br />
| beschmi<br />
| Stansted<br />
| 2007-01-10 6:40am<br />
| 4U2332<br />
|-<br />
|}<br />
<br />
== Accomodation ==<br />
<br />
3 of us are staying at<br />
<br />
* [http://www.activehotels.com/servlet/xmlbrochure/index.do?hotelid=116496& Eurobar Cafe & Hotel]<br />
<br />
It's quite close to the center of town, and near the bus stop and train<br />
station.<br />
<br />
Other close by places that look good include:<br />
<br />
* [http://www.lintonlodge.activehotels.com/BBA&subid=R1543223 Linton Lodge]<br />
* [http://www.cotswoldlodgehotel.activehotels.com/BBA&subid=R1543223 Cotswold Lodge]<br />
<br />
=== YHA ===<br />
I(pepe) will go YHA in order to save some Euros (I need to stay for four nights, due to the few Valencia-London flight choices). If anyone else will go to YHA too, we could make a joint reservation.<br />
<br />
The hostel seems to be quite close to center and train station too.<br />
<br />
People staying at a YHA hostel:<br />
* pepe</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Hac_2007/Attendees&diff=8956Hac 2007/Attendees2006-12-07T09:28:10Z<p>Mnislaih: Added my travel details</p>
<hr />
<div>Attendee list<br />
<br />
<br />
{|<br />
! Name<br />
! IRC nick<br />
! Dates<br />
! Projects<br />
|-<br />
| Don Stewart<br />
| dons<br />
| 10,11,12<br />
| Hackage, ByteStrings, stream fusion<br />
|-<br />
| Duncan Coutts<br />
| dcoutts<br />
| 10,11,12<br />
|<br />
|-<br />
| Ian Lynagh<br />
| Igloo<br />
| 10,11,12<br />
| GHC, Cabal, Hackage, and loads more besides<br />
|-<br />
| Neil Mitchell<br />
| ndm<br />
| 10,11,12<br />
| Yhc, Hoogle, Catch, Dr Haskell, WinHugs ...<br />
|-<br />
| Thorkil Naur<br />
| naur<br />
| 10,11,12<br />
| Integer implementation (GMP), Porting, Factorization, Puzzles<br />
|-<br />
| Pepe Iborra<br />
| mnislaih<br />
| 10,11,12<br />
| GHC, the GHCi debugger, Darcs does look sexy, infrastructure & tools.<br />
|-<br />
| Dominic Steinitz<br />
|<br />
| 10,11,12<br />
| crypto, networking<br />
|-<br />
| Ben Lippmeier<br />
|<br />
| 10,11,12<br />
| GHC bug squashing.<br />
|-<br />
| David Himmelstrup<br />
| Lemmih<br />
| 10,11,12<br />
| cabal-test, QuickCheck, Hackage, cabal-get.<br />
|-<br />
| Ross Paterson<br />
|<br />
| ?<br />
| Hackage<br />
|-<br />
| Simon Marlow<br />
|<br />
| ?<br />
|<br />
|- <br />
| Björn Bringert<br />
| bringert<br />
| 10,11,12<br />
| Hackage, libraries, QuickCheck 2, GHC<br />
|-<br />
|}<br />
<br />
<br />
<br />
== Arriving ==<br />
<br />
If you are arriving at Heathrow, and want to meet up for the trip up to<br />
Oxford, add you details here, so people can arrange to travel together:<br />
<br />
{|<br />
|-<br />
! Name<br />
! Airport<br />
! Arrival date/time<br />
! Flight <br />
|-<br />
| dons<br />
| Heathrow<br />
| 2007-01-10 6:20am<br />
| QF31<br />
|-<br />
| bringert<br />
| Heathrow<br />
| 2007-01-10 8:25am<br />
| SK523<br />
|-<br />
| pepe<br />
| Stansted<br />
| 2007-01-09 6:10pm<br />
| 3840<br />
|-<br />
|}</div>Mnislaihhttps://wiki.haskell.org/index.php?title=GHC/GHCi_debugger&diff=8837GHC/GHCi debugger2006-12-03T21:59:26Z<p>Mnislaih: Update with current status</p>
<hr />
<div>The GHCi Debugger project extends ghci with, well, debugging capabilities. Here is a [http://ender4.dsic.upv.es:81/ghcdocs/ghci.html snapshot] of the ghci documentation page extended with this project.<br />
<br />
This page is a dump of the designs, ideas, and results of the project. Check [http://darcs.haskell.org/SoC/ghc.debugger/demo.mov here] for a Quicktime video demonstrating the use of the debugger.<br />
<br />
== Current Status == <br />
The debugger is currently under development on beta stage, I continue working on it. It might be or might be not included on GHC 6.8, that will depend on what the GHC development team decide. The code is available on the repo (see at the bottom of the page) and I encourage you to build it and play with it.<br />
<br />
=== Feature Wise ===<br />
* Stack Traces have been dropped and are not being pursued currently<br />
* The Closure viewer includes support for everything in GHC, but currently GADTs might be problematic<br />
* Dynamic breakpoints are fully supported<br />
<br />
== Intermediate Closure Viewer ==<br />
The closure viewer is intended to permit working with polymorphic values in breakpoints, as well as to explore intermediate computations without altering the evaluation order.<br />
<br />
This feature is now (more or less) complete. Currently it provides two new commands under ghci, ''':print''' and ''':sprint''', both used in the same way as <tt>:type</tt> or <tt>:info</tt>. The latter prints a semievaluated closure using underscores to represent suspended computations (pretty much as [[Hood]] does). The former one in addition binds these thunks to variable names, so that you can do things with them.<br />
<br />
Example:<br />
<pre><br />
Prelude> let li = map Just [1..5]<br />
Prelude> length li<br />
5<br />
Prelude> :sp li<br />
li - [_,_,_,_,_,]<br />
<br />
Prelude> head li<br />
Just 1<br />
<br />
Prelude> :sp li<br />
li - [Just 1,_,_,_,_]<br />
<br />
Prelude> last li<br />
Just 5<br />
<br />
Prelude> :sp li<br />
li - [Just 1,_,_,_Just 5]<br />
<br />
Prelude> :p li<br />
li - [Just 1, (_t1::Maybe Integer),(_t2::Maybe Integer),(_t3::Maybe Integer),Just 5]<br />
<br />
Prelude> _t1 `seq` ()<br />
<br />
Prelude> :p li<br />
li - [Just 1, Just 2,(_t3::Maybe Integer),(_t4::Maybe Integer),Just 5]<br />
<br />
Prelude> _t2<br />
Just 3<br />
</pre><br />
<br />
Its best feature is that it can work without type information, so you can display polymorphic objects the type of which you don't know. However if there is type information available, it is used. Thanks to this it can work with opaque or coerced types. For instance:<br />
<br />
<haskell><br />
data Opaque = forall a. O a<br />
</haskell><br />
<br />
<pre><br />
*Test2> let li = map Just [1..5]<br />
*Test2> let o = O li<br />
*Test2> head li `seq` ()<br />
*Test2> length li `seq` ()<br />
*Test2> :p o<br />
o - [O Just 1,(_t1::Integer),(_t2::Integer),(_t3::Integer),(_t4::Integer)]<br />
</pre><br />
<br />
In the example above the <tt>li</tt> inside <tt>o</tt> has an opaque existential type. However, the closure viewer makes it possible to recover its type when it gets evaluated.<br />
<br />
Other currently proposed extensions are a <tt>safeCoerce</tt> function (not so useful, it depends on ghc-api) and an <tt>unsafeDeepSeq</tt> (this one is decoupled from ghc-api). There is also a generally useful (for compiler/tool developers) <tt>isFullyEvaluated</tt> query function. The signatures being:<br />
<br />
<pre><br />
isFullyEvaluated :: a -> IO Bool <br />
unsafeDeepSeq :: a -> b -> b <br />
safeCoerce :: GHC.Session -> a -> Maybe b<br />
</pre><br />
<br />
Finally, note that there are some inconveniences with the current implementation, such as <tt>:p</tt> binding the same closure to different names when used twice on the same closure, but they are minor and temporary (hopefully). <br />
<br />
<br />
== Usability ==<br />
There is plenty of work to be done in this area before the debugger can be shipped with ghc. <br />
<br />
If you have tried the patches maybe you want to add your comments here. Please add feature requests here too.<br />
<br />
== Dynamic Breakpoints ==<br />
<br />
See the user details of the current implementation at the GHC User Guide. Here is a [http://ender4.dsic.upv.es:81/ghcdocs/ghci.html snapshot] of the ghci documentation page extended with this project.<br />
<br />
<br />
=== Event sites and events ===<br />
We define 'event sites' as points in the code where you can want to set a breakpoint. Current candidates for sites are:<br />
* On the entrance to a function / lambda abstraction<br />
* <strike>Prior to function applications</strike> ''(this one does not make sense unless it forces the application using <tt>$!</tt>)<br />
* Local bindings in lets and wheres<br />
* Entrance to statements in monadic-do code<br />
<br />
Overlapping or unnecesary events should be coalesced into a single one. <br />
The rationale for what is an event and what is not is trying to find a middle point between the user interests and the overhead introduced:<br />
* We want to keep the overhead manageable, thus we want to keep the number of breakpoints low.<br />
* The user wants to introduce breakpoints at will.<br />
<br />
Credit goes to both A. Tolmach's ML debugger and the OCaml time-travel debugger for providing the inspiration.<br />
<br />
=== Proposals ===<br />
There are currently the following proposals:<br />
<br />
* Instrument the code with a conditional breakpoint at every event site. Sites are numbered, and the condition uses a site-indexed array to check if there is a breakpoint enabled. The array is maintained inside ghci. Hopefully not much magic is required for this one.<br />
<br />
* In the style of the previous one, but no array is maintained. All the breakpoint conditions are set to False, so almost no overhead is incurred. When the user demands a breakpoint, its BCO in the heap is rewritten to enable the breakpoint. Feasibility of this?<br />
<br />
* Don't use instrumentation. Have a new header for BCOs with breakpoints, say BCO_BREAK, and change headers in execution time on user demand (as in the previous proposal). The problem I see with this one is how to extract the local bindings. I don't fully grok the scheme Lemmih uses to do that yet.<br />
<br />
During this project we have explored the first one, under the lemma of ``do the simplest thing that could possibly work``. <br />
I'm sure there are many other designs. Please add your proposal or just throw an idea in.<br />
<br />
== Call Traces ==<br />
We want to have ''strict'' call traces, not the lazy ones. <br />
<br />
=== Proposals ===<br />
<br />
* It has been suggested that stealing ideas from Cost-Centre Stacks may be useful. I need more pointers on this.<br />
<strike><br />
* Based on Tolmach's debugger, we can instrument the source code to build a timeline of events (either lazily or not). The events contain a pointer to its lexical parent event. With that it should be possible to extract a call trace:<br />
# CASE 1: We are in a Function definition (FN):<br />
## Go back one step in the timeline: it necessarily is an application (APP)<br />
## Go back to its 'binding', i.e. its lexical parent. Keep doing this until it is a FN, then start again from case 1.<br />
## Once you reach the top, i.e. the 0 event, you are done. Display all theAPPs you encountered in the way<br />
# CASE 2: We are in a site other than a FN:<br />
## Go back [[lexically]] until you hit a FN and continue with case 1.<br />
<br />
This is just a wild, untested idea. It's possible that it would not work. Also even if it worked, it's possible that the overhead was unadmissible.<br />
</strike> WON'T WORK WITH LAZINESS<br />
<br />
== Integration ==<br />
Allowing other tools to integrate with the debugger is an important goal. It should not be taken lightly though.<br />
<br />
* It has been suggested to create a client/server protocol so that the debugger can be used by other tools.<br />
<br />
* On the other hand, arguably it would be much easier to provide integration to clients of the ghc-api via some form of debugger api.<br />
<br />
* Finally, it should be possible to derive the client/server architecture as an afterthought provided there is a debugger api in the ghc-api.<br />
<br />
== Further pointers ==<br />
<br />
# [http://www.tekno.chalmers.se/~murk/rectus Rectus], '' Oleg M&uuml;rk and Lennart Kolmodin''<br />
# [http://caml.inria.fr/pub/docs/manual-ocaml/manual030.html The Ocaml Debugger], ''The OCaml Team''<br />
# [http://web.cecs.pdx.edu/~apt/jfp95.ps A debugger for Standard ML], ''A.Tolmach, A. Appel''<br />
# [http://www.haskell.org//pipermail/cvs-ghc/2006-April/029040.html The original discussion in the ghc-cvs mailing list]<br />
<br />
== How to get the patches ==<br />
<br />
The patches are available at the SoC ghc.debugger [http://darcs.haskell.org/SoC/ghc.debugger/ darcs repo]:<br />
<pre><br />
darcs get --partial http://darcs.haskell.org/SoC/ghc.debugger<br />
</pre><br />
This is a modified version of GHC 6.6. Build it following the instructions at the [http://hackage.haskell.org/trac/ghc GHC developers wiki].<br />
<br />
If darcs-all does not do it for you, you will need to manually pull a few patches at the libraries/base repo, to be pulled from http://darcs.haskell.org/SoC/ghc.debugger/libraries/base<br />
<br />
Have fun! (and feel free to spam [mailto:mnislaih@gmail.com me] with bugs, suggestions or requests!)</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Haskell_Quiz/Bytecode_Compiler&diff=8166Haskell Quiz/Bytecode Compiler2006-11-10T18:35:38Z<p>Mnislaih: Added a link to my solution, and the Ruby wrapper for the haskell solution</p>
<hr />
<div>==The Problem==<br />
<br />
Create a bytecode compiler as described on this ruby quiz page: http://www.rubyquiz.com/quiz100.html<br />
<br />
Use this tester by Michael Sloan:<br />
<br />
<haskell><br />
fromBytes n xs =<br />
let int16 = (fromIntegral ((fromIntegral int32) :: Int16)) :: Int<br />
int32 = byte xs<br />
byte xs = foldl (\accum byte -> (accum `shiftL` 8) .|. (byte)) (head xs) (take (n - 1) (tail xs))<br />
in<br />
if n == 2<br />
then int16 <br />
else int32 <br />
<br />
interpret [] [] = error "no result produced"<br />
interpret (s1:s) [] = s1<br />
interpret s (o:xs) | o < 10 = interpret ((fromBytes (o*2) xs):s) (drop (o*2) xs)<br />
interpret (s1:s2:s) (o:xs)<br />
| o == 16 = interpret (s2:s1:s) xs<br />
| otherwise = interpret (((case o of 10 -> (+); 11 -> (-); 12 -> (*); 13 -> (^); 14 -> div; 15 -> mod) s2 s1):s) xs<br />
<br />
test :: (String -> [Int]) -> IO ()<br />
test f = assert "2+5" 7 >> assert "2-1" 1 >> assert "2*12" 24 >> assert "2^3" 8 >> assert "5/2" 2 >> assert "15%4" 3 >><br />
assert "2+2+2" 6 >> assert "2^8/4" 64 >> assert "3*11%3" 0 >><br />
assert "2*(3+4)" 14 >> assert "(3/3)+(8-2)" 7 >> assert "(1+3)/(2/2)*(10-8)" 8 >> assert "(10%3)*(2+2)" 4 >><br />
assert "(10/(2+3)*4)" 8 >> assert "5+((5*4)%(2+1))" 7 >> assert "-(2-3-5)" 6 >> assert "-1*-1" (1) >><br />
assert "1*-1" (-1) >> assert "1*-1" (-1) >> assert "-1*1" (-1) >><br />
assert "-1" (-1)<br />
where assert str val = print ((if (interpret [] $ f str) == val then "Passed: " else "Failed: ") ++ str)</haskell><br />
<br />
Or you can use the original Ruby test suite via this Ruby wrapper for your Haskell solution:<br />
<br />
<code><br />
class Compiler <br />
def Compiler.compile(arith)<br />
result = `runghc compiler.hs #{arith}`<br />
eval (result.strip.delete '"')<br />
end<br />
end<br />
</code><br />
<br />
==Solutions==<br />
<br />
* [[Haskell Quiz/Bytecode Compiler/Solution Michael Sloan|Michael Sloan]]<br />
<br />
* [[Haskell Quiz/Bytecode Compiler/Solution Justin Bailey|Justin Bailey]]<br />
<br />
* [[Haskell Quiz/Bytecode Compiler/Solution Pepe Iborra |Pepe Iborra]]<br />
<br />
* A (non-monadic) solution to the parsing and eval part of this quiz is a [http://www.cs.kent.ac.uk/people/staff/sjt/craft2e/Code/Parsing/Parsing.hs case study] in Chapter 17 of [http://www.cs.kent.ac.uk/people/staff/sjt/craft2e The Craft of Functional Programming] by Simon Thompson.</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Haskell_Quiz/Bytecode_Compiler/Solution_Pepe_Iborra&diff=8165Haskell Quiz/Bytecode Compiler/Solution Pepe Iborra2006-11-10T18:34:13Z<p>Mnislaih: </p>
<hr />
<div>This extremely simple solution declares the type of Expressions as an instance of Num, thus don't really need to define a parser as long as the compiler is launched interpreted via 'ghc -e' . This trick is inspired from the Ruby solution.<br />
<br />
As far as I know it passes all the tests in the original suite, but due to the parsing trick some expressions need parentization. Namely expressions with negations such as <hask>1*-1</hask>, which needs to be expressed as <hask>1*(-1)</hask>.<br />
<br />
In order to launch the compiler from the command line you should use the script: <br />
<br />
<code><br />
ghc bytecode.hs -fno-warn-missing-methods -e "process ($1)"<br />
</code><br />
And then:<br />
<code><br />
sh compiler.sh 1+2<br />
</code><br />
<br />
The solution: <br />
<br />
<haskell><br />
import Data.Bits<br />
import Prelude hiding ((**), mod,div,const)<br />
<br />
process :: Exp -> String<br />
process = output . flip generate [] <br />
<br />
data Exp = Exp :+ Exp<br />
| Exp :/ Exp<br />
| Exp :* Exp<br />
| Exp :- Exp<br />
| Exp :^ Exp<br />
| Exp :% Exp<br />
| Val Int<br />
deriving (Show, Eq)<br />
<br />
data ByteCode = Const Int<br />
| LConst Int<br />
| ADD<br />
| SUB<br />
| MUL<br />
| POW<br />
| DIV<br />
| MOD<br />
| SWAP<br />
deriving (Show,Eq)<br />
<br />
type Stack = [ByteCode]<br />
<br />
-------------------<br />
-- The "Parser"<br />
-------------------<br />
<br />
instance Fractional Exp where<br />
(/) = (:/)<br />
<br />
instance Num (Exp) where<br />
(+) = (:+)<br />
(-) = (:-)<br />
(*) = (:*)<br />
negate (Val i) = Val (negate i)<br />
fromInteger = Val . fromIntegral<br />
<br />
(**) = (:^)<br />
(%) = (:%) <br />
<br />
----------------------<br />
-- Smart constructors<br />
----------------------<br />
min_small = -32768<br />
max_small = 32767<br />
i `inBounds` (min,max) = i >= min && i <= max<br />
<br />
add,sub,mul,pow,div,mod,swap :: Stack -> Stack<br />
const i = if i `inBounds` (min_small,max_small) then Const i else LConst i<br />
add = (++[ADD])<br />
sub = (++[SUB])<br />
mul = (++[MUL])<br />
pow = (++[POW])<br />
div = (++[DIV])<br />
mod = (++[MOD])<br />
swap = (++[SWAP])<br />
<br />
---------------------<br />
<br />
generate :: Exp -> Stack -> Stack<br />
generate (Val i) = (++[const i])<br />
generate (x :+ y) = binaryOp x y add<br />
generate (x :- y) = binaryOp x y sub<br />
generate (x :* y) = binaryOp x y mul<br />
generate (x :/ y) = binaryOp x y div<br />
generate (x :^ y) = binaryOp x y pow<br />
generate (x :% y) = binaryOp x y mod<br />
<br />
binaryOp :: Exp -> Exp -> (Stack -> Stack) -> Stack -> Stack<br />
binaryOp x y f = f . generate y . generate x<br />
<br />
bytes :: Int -> [Int]<br />
bytes a = a .&. 255 : bytes (a `shiftR` 8)<br />
<br />
represent :: ByteCode -> [Int]<br />
represent (Const i) = 1 : reverse( take 2 (bytes i))<br />
represent (LConst i) = 2 : reverse( take 4 (bytes i))<br />
represent ADD = [10]<br />
represent SUB = [11]<br />
represent MUL = [12]<br />
represent POW = [13]<br />
represent DIV = [14]<br />
represent MOD = [15]<br />
represent SWAP= [160]<br />
<br />
output :: Stack -> String<br />
output = show . concatMap represent <br />
</haskell></div>Mnislaihhttps://wiki.haskell.org/index.php?title=Haskell_Quiz/Bytecode_Compiler/Solution_Pepe_Iborra&diff=8164Haskell Quiz/Bytecode Compiler/Solution Pepe Iborra2006-11-10T18:27:00Z<p>Mnislaih: </p>
<hr />
<div>This extremely simple solution declares the type of Expressions as an instance of Num, thus don't really need to define a parser as long as the compiler is launched interpreted via 'ghc -e' . This trick is inspired from the Ruby solution.<br />
<br />
As far as I know it passes all the tests in the original suite, but due to the parsing trick some expressions need parentization. Namely expressions with negations such as <hask>1*-1</hask>, which needs to be expressed as <hask>1*(-1)</hask>.<br />
<br />
In order to launch the compiler from the command line you should use the script: <br />
<br />
<code><br />
ghc bytecode.hs -fno-implicit-prelude -fno-warn-missing-methods -e "process ($1)"<br />
</code><br />
And then:<br />
<code><br />
sh compiler.sh 1+2<br />
</code><br />
<br />
The solution: <br />
<br />
<haskell><br />
import Data.Bits<br />
import Prelude hiding ((**), mod,div,const)<br />
<br />
process :: Exp -> String<br />
process = output . flip generate [] <br />
<br />
data Exp = Exp :+ Exp<br />
| Exp :/ Exp<br />
| Exp :* Exp<br />
| Exp :- Exp<br />
| Exp :^ Exp<br />
| Exp :% Exp<br />
| Val Int<br />
deriving (Show, Eq)<br />
<br />
data ByteCode = Const Int<br />
| LConst Int<br />
| ADD<br />
| SUB<br />
| MUL<br />
| POW<br />
| DIV<br />
| MOD<br />
| SWAP<br />
deriving (Show,Eq)<br />
<br />
type Stack = [ByteCode]<br />
<br />
-------------------<br />
-- The "Parser"<br />
-------------------<br />
<br />
instance Fractional Exp where<br />
(/) = (:/)<br />
<br />
instance Num (Exp) where<br />
(+) = (:+)<br />
(-) = (:-)<br />
(*) = (:*)<br />
negate (Val i) = Val (negate i)<br />
fromInteger = Val . fromIntegral<br />
<br />
(**) = (:^)<br />
(%) = (:%) <br />
<br />
----------------------<br />
-- Smart constructors<br />
----------------------<br />
min_small = -32768<br />
max_small = 32767<br />
i `inBounds` (min,max) = i >= min && i <= max<br />
<br />
add,sub,mul,pow,div,mod,swap :: Stack -> Stack<br />
const i = if i `inBounds` (min_small,max_small) then Const i else LConst i<br />
add = (++[ADD])<br />
sub = (++[SUB])<br />
mul = (++[MUL])<br />
pow = (++[POW])<br />
div = (++[DIV])<br />
mod = (++[MOD])<br />
swap = (++[SWAP])<br />
<br />
---------------------<br />
<br />
generate :: Exp -> Stack -> Stack<br />
generate (Val i) = (++[const i])<br />
generate (x :+ y) = binaryOp x y add<br />
generate (x :- y) = binaryOp x y sub<br />
generate (x :* y) = binaryOp x y mul<br />
generate (x :/ y) = binaryOp x y div<br />
generate (x :^ y) = binaryOp x y pow<br />
generate (x :% y) = binaryOp x y mod<br />
<br />
binaryOp :: Exp -> Exp -> (Stack -> Stack) -> Stack -> Stack<br />
binaryOp x y f = f . generate y . generate x<br />
<br />
bytes :: Int -> [Int]<br />
bytes a = a .&. 255 : bytes (a `shiftR` 8)<br />
<br />
represent :: ByteCode -> [Int]<br />
represent (Const i) = 1 : reverse( take 2 (bytes i))<br />
represent (LConst i) = 2 : reverse( take 4 (bytes i))<br />
represent ADD = [10]<br />
represent SUB = [11]<br />
represent MUL = [12]<br />
represent POW = [13]<br />
represent DIV = [14]<br />
represent MOD = [15]<br />
represent SWAP= [160]<br />
<br />
output :: Stack -> String<br />
output = show . concatMap represent <br />
</haskell></div>Mnislaihhttps://wiki.haskell.org/index.php?title=Haskell_Quiz/Bytecode_Compiler/Solution_Pepe_Iborra&diff=8163Haskell Quiz/Bytecode Compiler/Solution Pepe Iborra2006-11-10T18:24:04Z<p>Mnislaih: </p>
<hr />
<div>This extremely simple solution declares the type of Expressions as an instance of Num, thus don't really need to define a parser as long as the compiler is launched interpreted via 'ghc -e' . This trick is inspired from the Ruby solution.<br />
<br />
It passes all the tests but due to the parsing trick some expressions need parentization. Namely expressions with negations such as "1*-1", which needs to be expressed as "1*(-1)".<br />
<br />
In order to launch the compiler from the command line you should use the script: <br />
<code><br />
ghc bytecode.hs -fno-implicit-prelude -fno-warn-missing-methods -e "process ($1)"<br />
</code><br />
And then:<br />
<code><br />
sh compiler.sh 1+2<br />
</code><br />
<br />
<haskell><br />
import Data.Bits<br />
import Prelude hiding ((**), mod,div,const)<br />
<br />
process :: Exp -> String<br />
process = output . flip generate [] <br />
<br />
data Exp = Exp :+ Exp<br />
| Exp :/ Exp<br />
| Exp :* Exp<br />
| Exp :- Exp<br />
| Exp :^ Exp<br />
| Exp :% Exp<br />
| Val Int<br />
deriving (Show, Eq)<br />
<br />
data ByteCode = Const Int<br />
| LConst Int<br />
| ADD<br />
| SUB<br />
| MUL<br />
| POW<br />
| DIV<br />
| MOD<br />
| SWAP<br />
deriving (Show,Eq)<br />
<br />
type Stack = [ByteCode]<br />
<br />
-------------------<br />
-- The "Parser"<br />
-------------------<br />
<br />
instance Fractional Exp where<br />
(/) = (:/)<br />
<br />
instance Num (Exp) where<br />
(+) = (:+)<br />
(-) = (:-)<br />
(*) = (:*)<br />
negate (Val i) = Val (negate i)<br />
fromInteger = Val . fromIntegral<br />
<br />
(**) = (:^)<br />
(%) = (:%) <br />
<br />
----------------------<br />
-- Smart constructors<br />
----------------------<br />
min_small = -32768<br />
max_small = 32767<br />
<br />
i `inBounds` (min,max) = i >= min && i <= max<br />
<br />
add,sub,mul,pow,div,mod,swap :: Stack -> Stack<br />
const i = if i `inBounds` (min_small,max_small) then Const i else LConst i<br />
add = (++[ADD])<br />
sub = (++[SUB])<br />
mul = (++[MUL])<br />
pow = (++[POW])<br />
div = (++[DIV])<br />
mod = (++[MOD])<br />
swap = (++[SWAP])<br />
<br />
---------------------<br />
<br />
generate :: Exp -> Stack -> Stack<br />
generate (Val i) = (++[const i])<br />
generate (x :+ y) = binaryOp x y add<br />
generate (x :- y) = binaryOp x y sub<br />
generate (x :* y) = binaryOp x y mul<br />
generate (x :/ y) = binaryOp x y div<br />
generate (x :^ y) = binaryOp x y pow<br />
generate (x :% y) = binaryOp x y mod<br />
<br />
binaryOp :: Exp -> Exp -> (Stack -> Stack) -> Stack -> Stack<br />
binaryOp x y f = f . generate y . generate x<br />
<br />
bytes :: Int -> [Int]<br />
bytes a = a .&. 255 : bytes (a `shiftR` 8)<br />
<br />
represent :: ByteCode -> [Int]<br />
represent (Const i) = 1 : reverse( take 2 (bytes i))<br />
represent (LConst i) = 2 : reverse( take 4 (bytes i))<br />
represent ADD = [10]<br />
represent SUB = [11]<br />
represent MUL = [12]<br />
represent POW = [13]<br />
represent DIV = [14]<br />
represent MOD = [15]<br />
represent SWAP= [160]<br />
<br />
output :: Stack -> String<br />
output = show . concatMap represent <br />
</haskell></div>Mnislaihhttps://wiki.haskell.org/index.php?title=Haskell_Quiz/Bytecode_Compiler/Solution_Pepe_Iborra&diff=8162Haskell Quiz/Bytecode Compiler/Solution Pepe Iborra2006-11-10T18:21:17Z<p>Mnislaih: </p>
<hr />
<div>This solution declares the type of Expressions as an instance of Num, thus don't really need to define a parser as long as the compiler is launched interpreted via 'ghc -e' . This trick is inspired from the Ruby solution.<br />
<br />
It passes all the tests but due to the parsing trick some expressions need parentization. Namely expressions with negations such as "1*-1", which needs to be expressed as "1*(-1)".<br />
<br />
In order to launch the compiler from the command line you should use the script: <br />
<code><br />
ghc bytecode.hs -fno-implicit-prelude -fno-warn-missing-methods -e 'process ($1)'<br />
</code><br />
<haskell><br />
</haskell></div>Mnislaihhttps://wiki.haskell.org/index.php?title=Debugging&diff=5855Debugging2006-09-06T22:38:34Z<p>Mnislaih: </p>
<hr />
<div>== Printf and friends ==<br />
The simplest approach is to use <tt>Debug.Trace.trace</tt>:<br />
<pre><br />
trace :: String -> a -> a<br />
</pre><br />
: "''When called, trace outputs the string in its first argument, before returning the second argument as its result.'"<br />
<br />
A common idiom to trace a function is:<br />
<pre><br />
myfun a b | trace ("myfun " ++ show a ++ " " ++ show b) False = undefined<br />
myfun a b = ...<br />
</pre><br />
The advantage is that disabling and enabling the trace takes only one line comment.<br />
<br />
You must keep in mind that due to lazy evaluation your traces will only print if the value they wrap is ever demanded.<br />
<br />
<br />
A more powerful<br />
alternative for this approach is [http://www.haskell.org/hood Hood]. Even if it hasn't been<br />
updated in some time, Hood works perfectly with the current ghc<br />
distribution. Even more, Hugs has it already integrated, see the [http://cvs.haskell.org/Hugs/pages/users_guide/observe.html manual page]. Add an <tt>import Observe</tt> and start inserting observations in your code.<br />
For instance:<br />
<pre><br />
import Hugs.Observe<br />
<br />
f' = observe "Informative name for f" f <br />
f x = if odd x then x*2 else 0<br />
</pre><br />
And then in hugs:<br />
<pre><br />
Main> map f' [1..5]<br />
[2,0,6,0,10]<br />
<br />
>>>>>>> Observations <<<<<<<br />
<br />
Informative name for f<br />
{ \ 5 -> 10<br />
, \ 4 -> 0<br />
, \ 3 -> 6<br />
, \ 2 -> 0<br />
, \ 1 -> 2<br />
}<br />
<br />
</pre><br />
<br />
outputs a report of all the invocations of f and their result.<br />
<br />
I have a handy bogus Hugs.Observe module with no-ops for the observations so that I don't need to remove them manually, expecting that the compiler will optimize them away. <br />
<br />
<br />
== Offline analysis of traces ==<br />
The most advanced debugging tools are based in offline analysis of traces. [http://www.haskell.org/hat Hat] is probably the most up-to-date tool for this, offering a comprehensive set of tools. [[User:NeilMitchell|Neil Mitchell]] has made available a Windows port of Hat at [http://www-users.cs.york.ac.uk/~ndm/projects/windows.php his site].<br />
<br />
The disadvantage of these tools is that they are not always compatible with the latest libraries, so you can put them to use only in some cases. <br />
<br />
''Some Hat user should complete this section''<br />
<br />
== Dynamic breakpoints in GHCi == <br />
Finally, the [[GHC/GHCiDebugger]] project aims to bring dynamic<br />
breakpoints and intermediate values observation to GHCi in a near<br />
future. Right now the tool is only available from the site as a<br />
modified version of GHC, so unfortunately you will have to compile it<br />
yourself if you want to have it.<br />
<br />
This tool allows to set breakpoints in your code, directly from the GHCi command prompt. An example session:<br />
<pre><br />
*main:Main> :break add Main 2<br />
Breakpoint set at (2,15)<br />
*main:Main> qsort [10,9..1]<br />
Local bindings in scope:<br />
x :: a, xs :: [a], left :: [a], right :: [a]<br />
<br />
qsort2.hs:2:15-46> :sprint x<br />
x = _<br />
qsort2.hs:2:15-46> x<br />
This is an untyped, unevaluated computation. You can use seq to <br />
force its evaluation and then :print to recover its type<br />
qsort2.hs:2:15-46> seq x ()<br />
() <br />
qsort2.hs:2:15-46> :p x<br />
x - 10<br />
</pre><br />
<br />
Once a breakpoint is hit, you can explore the bindings in scope, as well as to evaluate any haskell expression, as you would do in a normal GHCi prompt. The <tt>':print'</tt> command can be very useful to explore the lazyness of your code.<br />
<br />
== Catching Assert trick ==<br />
<br />
See the mail [http://www.mail-archive.com/haskell-cafe@haskell.org/msg13034.html message].<br />
<br />
== Other tricks ==<br />
* If you use GHC, you can get a stack trace in the console when your program fails with an error condition. See the [http://www.haskell.org/ghc/docs/latest/html/users_guide/runtime-control.html#rts-options-debugging manual page]</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Debugging&diff=5854Debugging2006-09-06T22:37:37Z<p>Mnislaih: </p>
<hr />
<div>== Printf and friends ==<br />
The simplest approach is to use <tt>Debug.Trace.trace</tt>:<br />
<pre><br />
trace :: String -> a -> a<br />
</pre><br />
: "''When called, trace outputs the string in its first argument, before returning the second argument as its result.'"<br />
<br />
A common idiom to trace a function is:<br />
<pre><br />
myfun a b | trace ("myfun " ++ show a ++ " " ++ show b) False = undefined<br />
myfun a b = ...<br />
</pre><br />
The advantage is that disabling and enabling the trace takes only one line comment.<br />
<br />
You must keep in mind that due to lazy evaluation your traces will only print if the value they wrap is ever demanded.<br />
<br />
<br />
A more powerful<br />
alternative for this approach is [[www.haskell.org/hood Hood]]. Even if it hasn't been<br />
updated in some time, Hood works perfectly with the current ghc<br />
distribution. Even more, Hugs has it already integrated, see the [http://cvs.haskell.org/Hugs/pages/users_guide/observe.html manual page]. Add an <tt>import Observe</tt> and start inserting observations in your code.<br />
For instance:<br />
<pre><br />
import Hugs.Observe<br />
<br />
f' = observe "Informative name for f" f <br />
f x = if odd x then x*2 else 0<br />
</pre><br />
And then in hugs:<br />
<pre><br />
Main> map f' [1..5]<br />
[2,0,6,0,10]<br />
<br />
>>>>>>> Observations <<<<<<<br />
<br />
Informative name for f<br />
{ \ 5 -> 10<br />
, \ 4 -> 0<br />
, \ 3 -> 6<br />
, \ 2 -> 0<br />
, \ 1 -> 2<br />
}<br />
<br />
</pre><br />
<br />
outputs a report of all the invocations of f and their result.<br />
<br />
I have a handy bogus Hugs.Observe module with no-ops for the observations so that I don't need to remove them manually, expecting that the compiler will optimize them away. <br />
<br />
<br />
== Offline analysis of traces ==<br />
The most advanced debugging tools are based in offline analysis of traces. [http://www.haskell.org/hat Hat] is probably the most up-to-date tool for this, offering a comprehensive set of tools. [[User:NeilMitchell|Neil Mitchell]] has made available a Windows port of Hat at [http://www-users.cs.york.ac.uk/~ndm/projects/windows.php his site].<br />
<br />
The disadvantage of these tools is that they are not always compatible with the latest libraries, so you can put them to use only in some cases. <br />
<br />
''Some Hat user should complete this section''<br />
<br />
== Dynamic breakpoints in GHCi == <br />
Finally, the [[GHC/GHCiDebugger]] project aims to bring dynamic<br />
breakpoints and intermediate values observation to GHCi in a near<br />
future. Right now the tool is only available from the site as a<br />
modified version of GHC, so unfortunately you will have to compile it<br />
yourself if you want to have it.<br />
<br />
This tool allows to set breakpoints in your code, directly from the GHCi command prompt. An example session:<br />
<pre><br />
*main:Main> :break add Main 2<br />
Breakpoint set at (2,15)<br />
*main:Main> qsort [10,9..1]<br />
Local bindings in scope:<br />
x :: a, xs :: [a], left :: [a], right :: [a]<br />
<br />
qsort2.hs:2:15-46> :sprint x<br />
x = _<br />
qsort2.hs:2:15-46> x<br />
This is an untyped, unevaluated computation. You can use seq to <br />
force its evaluation and then :print to recover its type<br />
qsort2.hs:2:15-46> seq x ()<br />
() <br />
qsort2.hs:2:15-46> :p x<br />
x - 10<br />
</pre><br />
<br />
Once a breakpoint is hit, you can explore the bindings in scope, as well as to evaluate any haskell expression, as you would do in a normal GHCi prompt. The <tt>':print'</tt> command can be very useful to explore the lazyness of your code.<br />
<br />
== Catching Assert trick ==<br />
<br />
See the mail [http://www.mail-archive.com/haskell-cafe@haskell.org/msg13034.html message].<br />
<br />
== Other tricks ==<br />
* If you use GHC, you can get a stack trace in the console when your program fails with an error condition. See the [http://www.haskell.org/ghc/docs/latest/html/users_guide/runtime-control.html#rts-options-debugging manual page]</div>Mnislaihhttps://wiki.haskell.org/index.php?title=Debugging&diff=5843Debugging2006-09-06T11:05:01Z<p>Mnislaih: Initial contribution</p>
<hr />
<div>== Printf and friends ==<br />
The simplest approach is to use <tt>Debug.Trace.trace</tt>:<br />
<pre><br />
trace :: String -> a -> a<br />
</pre><br />
: "''When called, trace outputs the string in its first argument, before returning the second argument as its result.'"<br />
<br />
A common idiom to trace a function is:<br />
<pre><br />
myfun a b | trace ("myfun " ++ show a ++ " " ++ show b) False = undefined<br />
myfun a b = ...<br />
</pre><br />
The advantage is that disabling and enabling the trace takes only one line comment.<br />
<br />
You must keep in mind that due to lazy evaluation your traces will only print if the value they wrap is ever demanded.<br />
<br />
<br />
A more powerful<br />
alternative for this approach is Hood [2]. Even if it hasn't been<br />
updated in some time, Hood works perfectly with the current ghc<br />
distribution. Even more, Hugs has it already integrated, see the [http://cvs.haskell.org/Hugs/pages/users_guide/observe.html manual page]. You can<br />
simply <tt>import Observe</tt> and use observations directly in your program.<br />
For instance:<br />
<pre><br />
import Hugs.Observe<br />
<br />
f' = observe "Informative name for f" f <br />
f x = if odd x then x*2 else 0<br />
</pre><br />
And then in hugs:<br />
<pre><br />
Main> map f' [1..5]<br />
[2,0,6,0,10]<br />
<br />
>>>>>>> Observations <<<<<<<br />
<br />
Informative name for f<br />
{ \ 5 -> 10<br />
, \ 4 -> 0<br />
, \ 3 -> 6<br />
, \ 2 -> 0<br />
, \ 1 -> 2<br />
}<br />
<br />
</pre><br />
<br />
outputs a report of all the invocations of f and their result:<br />
<br />
<br />
== Offline analysis of traces ==<br />
The most advanced debugging tools are based in offline analysis of traces. [http://www.haskell.org/hat Hat] is probably the most up-to-date tool for this, offering a comprehensive set of tools. [[User:NeilMitchell|Neil Mitchell]] has made available a Windows port of Hat at [http://www-users.cs.york.ac.uk/~ndm/projects/windows.php his site].<br />
<br />
The disadvantage of these tools is that they are not always compatible with the latest libraries, so you can put them to use only in some cases. <br />
<br />
''Some Hat user should complete this section''<br />
<br />
== Dynamic breakpoints in GHCi == <br />
Finally, the [[GHC/GHCiDebugger]] project aims to bring dynamic<br />
breakpoints and intermediate values observation to GHCi in a near<br />
future. Right now the tool is only available from the site as a<br />
modified version of GHC, so unfortunately you will have to compile it<br />
yourself if you want to have it.<br />
<br />
This tool allows to set breakpoints in your code, directly from the GHCi command prompt. An example session:<br />
<pre><br />
*main:Main> :break add Main 2<br />
Breakpoint set at (2,15)<br />
*main:Main> qsort [10,9..1]<br />
Local bindings in scope:<br />
x :: a, xs :: [a], left :: [a], right :: [a]<br />
<br />
qsort2.hs:2:15-46> :sprint x<br />
x = _<br />
qsort2.hs:2:15-46> x<br />
This is an untyped, unevaluated computation. You can use seq to <br />
force its evaluation and then :print to recover its type<br />
qsort2.hs:2:15-46> seq x ()<br />
() <br />
qsort2.hs:2:15-46> :p x<br />
x - 10<br />
</pre><br />
<br />
Once a breakpoint is hit, you can explore the bindings in scope, as well as to evaluate any haskell expression, as you would do in a normal GHCi prompt. The <tt>':print'</tt> command can be very useful to explore the lazyness of your code.<br />
<br />
== Other tricks ==<br />
* If you use GHC, you can get a stack trace in the console when your program fails with an error condition. See the [http://www.haskell.org/ghc/docs/latest/html/users_guide/runtime-control.html#rts-options-debugging manual page]</div>Mnislaih