https://wiki.haskell.org/api.php?action=feedcontributions&user=Steshaw&feedformat=atom
HaskellWiki - User contributions [en]
2024-03-19T10:56:52Z
User contributions
MediaWiki 1.35.5
https://wiki.haskell.org/index.php?title=Performance/Monads&diff=64202
Performance/Monads
2021-04-16T23:51:00Z
<p>Steshaw: /* Use Continuation Passing Style */ fix hyperlink to paper</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.<br />
<br />
== Use [[Continuation | Continuation Passing Style]] ==<br />
<br />
It is well known that every monad can be "embedded" into the continuation passing monad, Cont. All that is necessary is to make the "answer type" of the Cont monad be the desired monad, e.g.<br />
<haskell><br />
type MCPS a = forall r. Cont (M r) a<br />
<br />
runMCPS m = runCont m return<br />
</haskell><br />
Note that this is just essentially just ContT M and indeed all of the below is just writing out the ContT implementation.<br />
<br />
Also note that M's (>>=) operation isn't used. It comes up when you implement the other operations M supports.<br />
<br />
In many cases, this will effectively avoid a layer of interpretation in much of the code using M. To see this, let's look at code that would benefit from using the Maybe monad.<br />
<haskell><br />
liftMaybe2 :: (a -> b -> Maybe c) -> Maybe a -> Maybe b -> Maybe c<br />
liftMaybe2 f a b =<br />
case a of<br />
Nothing -> Nothing<br />
Just a' -> case b of<br />
Nothing -> Nothing<br />
Just b' -> f a' b'<br />
</haskell><br />
<br />
This code screams for using Maybe as a monad in which case it will look like,<br />
<haskell><br />
liftMaybe2 f a b = do<br />
a' <- a<br />
b' <- b<br />
f a' b'<br />
</haskell><br />
<br />
One things to note about the original code is that it must constantly check the returned value even though a failure (Nothing) is most likely a rare occurrence, and further more it's possible that we will need to propagate a Nothing through an arbitrary large amount of code, though a lot of times this won't happen.<br />
<br />
Ideally, we want "failure free" code to run as normal and only deal with failure when it occurs and ''immediately'' fail in those cases rather than propagating the failure. This is what using continuation passing style gets us.<br />
<br />
Explicitly expanding Cont we get,<br />
<haskell><br />
newtype MaybeCPS a = MaybeCPS { unMaybeCPS :: forall r. (a -> Maybe r) -> Maybe r }<br />
<br />
runMaybeCPS m = unMaybeCPS m return<br />
<br />
-- The Cont definitions of return and (>>=)<br />
instance Monad MaybeCPS where<br />
return a = MaybeCPS (\k -> k a)<br />
MaybeCPS m >>= f = MaybeCPS (\k -> m (\a -> unMaybeCPS (f a) k))<br />
</haskell><br />
<br />
Note that this code is just normal CPS code and completely independent of the Maybe monad. There are no case analyses. So, "failure free" code will run as normal (CPS) code.<br />
<br />
How and why does this work? We're basically specializing <hask>>>=</hask>. Before, we had<br />
<haskell><br />
m >>= f = case m of<br />
Just a -> f a<br />
Nothing -> Nothing<br />
</haskell><br />
i.e. the monadic bind does a case analysis on how to proceed. In the CPS-representation, we're specializing bind to the two possible constructors:<br />
<haskell><br />
return' a := (return a >>=) = (Just a >>=) = \f -> f a<br />
mzero' := (mzero >>=) = (Nothing >>=) = \f -> Nothing<br />
</haskell><br />
and the case analysis is now "built-in" into <hask>return'</hask> and <hask>mzero'</hask>. In general, embedding a monad in <hask>Cont</hask> specializes <hask>>>=</hask> to its primitive operations, like for example <hask>mzero</hask> or <hask>get</hask>. This is close to specifying the operational semantics of <hask>>>=</hask> directly and can hence be used to implement the monad in the first place, too.<br />
<br />
Now we need to implement the operations.<br />
<haskell><br />
instance MonadPlus MaybeCPS where<br />
mzero = MaybeCPS (\_ -> Nothing) -- equivalent to MaybeCPS (Nothing >>=)<br />
m `mplus` n = case runMaybeCPS m of<br />
Nothing -> n<br />
Just a -> return a<br />
</haskell><br />
<br />
There are two things to note about this code. mplus is where we use the case analysis. mplus is the only place that we look at what was returned and to do it we have to actually run the computation. This means that we only deal with "effects" when we need to. Further, mzero discards its continuation. This is the typical pattern for aborting a computation in CPS and will lead to an ''immediate'' termination of the computation.<br />
<br />
MaybeCPS should be faster than using Maybe in most cases and should be almost a drop in replacement for Maybe. Unfortunately, this [http://www.mail-archive.com/haskell-cafe@haskell.org/msg65857.html may not necessarily be true]. Usually, using a CPS implementation would be a drop in replacement, but Maybe is not an abstract data type. Anyway, some results for a more complicated example are [http://r6.ca/blog/20071028T162529Z.html here].<br />
<br />
See also [http://www.janis-voigtlaender.eu/Voi08d.html Asymptotic Improvement of Computations over Free Monads].<br />
<br />
See also [[Codensity Monad]]</div>
Steshaw
https://wiki.haskell.org/index.php?title=Generalised_algebraic_datatype&diff=63280
Generalised algebraic datatype
2020-04-16T01:46:23Z
<p>Steshaw: /* Papers */ fix link to GHC docs</p>
<hr />
<div>{{GHCUsersGuide|glasgow_exts|generalised-algebraic-data-types-gadts|a GADTs section}}<br />
<br />
== Papers ==<br />
<br />
See also [[Research papers/Type systems#Generalised Algebraic Data Types (GADTs)|research papers on type systems]].<br />
<br />
* A short description on generalised algebraic datatypes here [https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#generalised-algebraic-data-types-gadts as GHC language features].<br />
* Another description with links on [http://prime.haskell.org/wiki/GADTs Haskell' wiki].<br />
* [http://ecommons.library.cornell.edu/handle/1813/5614 First-Class Phantom Types] by James Cheney and Ralf Hinze<br />
* [http://cristal.inria.fr/~fpottier/publis/pottier-regis-gianas-05.pdf Stratified type inference for generalized algebraic data types] by François Pottier and Yann Régis-Gianas. It contains also a lot of links to other papers on GADTs.<br />
* [http://research.microsoft.com/en-us/um/people/simonpj/papers/gadt/index.htm Simple unification-based type inference for GADTs] by Simon Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, and Geoffrey Washburn. (Revised April 2006.)<br />
* [http://www.cs.mu.oz.au/~sulzmann/manuscript/simple-translate-gadts.ps Translating Generalized Algebraic Data Types to System F] written by [http://www.cs.mu.oz.au/~sulzmann/ Martin Sulzmann] and Meng Wang. [http://www.cs.mu.oz.au/~sulzmann/2005.html Many other papers]. The talk mentions also the notion of [[phantom type]], and [[existential type]], and [[type witness]].<br />
<br />
== Motivating example ==<br />
<br />
Generalised Algebraic Datatypes (GADTs) are datatypes for which a constructor has a non standard type. Indeed, in type systems incorporating GADTs, there are very few restrictions on the type that the data constructors can take. To show you how this could be useful, we will implement an evaluator for the typed SK calculus. Note that the K combinator is operationally similar to<br />
<math>\lambda\;x\;y\;.\;x</math><br />
and, similarly, S is similar to the combinator<br />
<math>\lambda\;x\;y\;z\;.\;x\;z\;(\;y\;z\;)</math><br />
which, in simply typed lambda calculus, have types<br />
<math>a \rightarrow b \rightarrow a </math><br />
and<br />
<math>(a \rightarrow b \rightarrow c) \rightarrow (a \rightarrow b) \rightarrow a \rightarrow c </math><br />
Without GADTs we would have to write something like this:<br />
<haskell><br />
data Term = K | S | Term :@ Term <br />
infixl 6 :@<br />
</haskell><br />
With GADTs, however, we can have the terms carry around more type information and create more interesting terms, like so:<br />
<haskell><br />
data Term x where<br />
K :: Term (a -> b -> a)<br />
S :: Term ((a -> b -> c) -> (a -> b) -> a -> c)<br />
Const :: a -> Term a<br />
(:@) :: Term (a -> b) -> (Term a) -> Term b<br />
infixl 6 :@<br />
</haskell><br />
now we can write a small step evaluator:<br />
<haskell><br />
eval::Term a -> Term a<br />
eval (K :@ x :@ y) = x<br />
eval (S :@ x :@ y :@ z) = x :@ z :@ (y :@ z)<br />
eval x = x<br />
</haskell><br />
Since the types of the so-called object language, being the typed SK calculus, are mimicked by the type system in our meta language, being Haskell, we have a pretty convincing argument that the evaluator won't mangle our types. We say that typing is preserved under evaluation (preservation.) Note that this is an argument and not a proof.<br />
<br />
This, however, comes at a price: let's see what happens when you try to convert strings into our object language:<br />
<haskell><br />
parse "K" = K<br />
parse "S" = S<br />
</haskell><br />
you'll get a nasty error like so:<br />
<br />
Occurs check: cannot construct the infinite type: c = b -> c<br />
Expected type: Term ((a -> b -> c) -> (a -> b) -> a -> b -> c)<br />
Inferred type: Term ((a -> b -> c) -> (a -> b) -> a -> c)<br />
In the definition of `foo': foo "S" = S<br />
<br />
One could, however, reason that parse has type: <hask>String -> exists a. Term a</hask>, see also [[Existential type]].<br />
<br />
== Example with lists ==<br />
<br />
here's another, smaller example:<br />
<haskell><br />
data Empty<br />
data NonEmpty<br />
data List x y where<br />
Nil :: List a Empty<br />
Cons:: a -> List a b -> List a NonEmpty<br />
<br />
safeHead:: List x NonEmpty -> x<br />
safeHead (Cons a b) = a<br />
</haskell><br />
<br />
now safeHead can only be applied to non empty lists, and will never evaluate to bottom. This too comes at a cost; consider the function:<br />
<br />
<haskell><br />
silly 0 = Nil<br />
silly 1 = Cons 1 Nil<br />
</haskell><br />
<br />
yields an objection from ghc:<br />
Couldn't match `Empty' against `NonEmpty'<br />
Expected type: List a Empty<br />
Inferred type: List a NonEmpty<br />
In the application `Cons 1 Nil'<br />
In the definition of `silly': silly 1 = Cons 1 Nil<br />
<br />
== Parsing Example ==<br />
<br />
Note that GADTs provide a rather nice platform for embedded domain specific languages. In particular, they allow an [[EDSL]] to use Haskell's type system for its own purposes. As a simple example, we might have an EDSL for simple (regexp-like) parsers that looks something like:<br />
<br />
<haskell><br />
data Parser tok a where<br />
Zero :: Parser tok ()<br />
One :: Parser tok ()<br />
Check :: (tok -> Bool) -> Parser tok tok<br />
Satisfy :: ([tok] -> Bool) -> Parser tok [tok]<br />
Push :: tok -> Parser tok a -> Parser tok a<br />
Plus :: Parser tok a -> Parser tok b -> Parser tok (Either a b)<br />
Times :: Parser tok a -> Parser tok b -> Parser tok (a,b)<br />
Star :: Parser tok a -> Parser tok [a]<br />
</haskell><br />
<br />
An evaluator/parser is then straightforward. Below it's written monadically for<br />
convenience, but this also means that we could generalise the return type to being in any MonadPlus. Note that an advantage of this representation which we don't show here is that we could also write a function which applies algebraic rules to the structure to try to simplify the parser before running it. (Though if we were really concerned with efficiency, we'd probably also need a couple more primitives.)<br />
<br />
<haskell><br />
parse :: Parser tok a -> [tok] -> Maybe a<br />
<br />
-- Zero always fails.<br />
parse Zero ts = mzero<br />
<br />
-- One matches only the empty string.<br />
parse One [] = return ()<br />
parse One _ = mzero<br />
<br />
-- Check p matches a string with exactly one token t such that p t holds.<br />
parse (Check p) [t] = if p t then return t else mzero<br />
parse (Check p) _ = mzero<br />
<br />
-- Satisfy p any string such that p ts holds.<br />
parse (Satisfy p) xs = if p xs then return xs else mzero<br />
<br />
-- Push t x matches a string ts when x matches (t:ts).<br />
parse (Push t x) ts = parse x (t:ts)<br />
<br />
-- Plus x y matches when either x or y does.<br />
parse (Plus x y) ts = liftM Left (parse x ts) `mplus` liftM Right (parse y ts)<br />
<br />
-- Times x y matches the concatenation of x and y.<br />
parse (Times x y) [] = liftM2 (,) (parse x []) (parse y [])<br />
parse (Times x y) (t:ts) = <br />
parse (Times (Push t x) y) ts `mplus`<br />
liftM2 (,) (parse x []) (parse y (t:ts))<br />
<br />
-- Star x matches zero or more copies of x.<br />
parse (Star x) [] = return []<br />
parse (Star x) (t:ts) = do<br />
(v,vs) <- parse (Times x (Star x)) (t:ts)<br />
return (v:vs)<br />
</haskell><br />
<br />
Finally, we might define some examples:<br />
<br />
<haskell><br />
token x = Check (== x)<br />
string xs = Satisfy (== xs)<br />
<br />
p = Times (token 'a') (token 'b')<br />
p1 = Times (Star (token 'a')) (Star (token 'b'))<br />
p2 = Star p1<br />
<br />
blocks :: (Eq tok) => Parser tok [[tok]]<br />
blocks = Star (Satisfy allEqual)<br />
where allEqual xs = and (zipWith (==) xs (drop 1 xs))<br />
<br />
evenOdd = Plus (Star (Times (Check even) (Check odd)))<br />
(Star (Times (Check odd) (Check even)))<br />
<br />
</haskell><br />
<br />
Testing this in ghci:<br />
<pre><br />
*Main> parse p "ab"<br />
Just ('a','b')<br />
*Main> parse p "ac"<br />
Nothing<br />
*Main> parse p1 "aaabbbb"<br />
Just ("aaa","bbbb")<br />
*Main> parse p2 "aaabbbbaabbbbbbbaaabbabab"<br />
Just [("aaa","bbbb"),("aa","bbbbbbb"),("aaa","bb"),("a","b"),("a","b")]<br />
*Main> :t p2<br />
p2 :: Parser Char [([Char], [Char])]<br />
*Main> parse blocks "aaaabbbbbbbbcccccddd"<br />
Just ["aaaa","bbbbbbbb","ccccc","ddd"]<br />
*Main> parse evenOdd [0..9]<br />
Just (Left [(0,1),(2,3),(4,5),(6,7),(8,9)])<br />
*Main> parse evenOdd [1..10]<br />
Just (Right [(1,2),(3,4),(5,6),(7,8),(9,10)])<br />
<br />
</pre><br />
<br />
== Projects containing GADTs ==<br />
<br />
Papers on [[Libraries and tools/Database interfaces/HaskellDB|HaskellDB]] describe problems when GADTs can help (but HaskellDB solves these problems with [[phantom type]]s).<br />
<br />
[[Darcs]] represents motivating examples for GADTs, too -- and uses them.<br />
The motivations are described in David Roundy's FOSDEM slides ([http://physics.oregonstate.edu/~roundyd/talks/fosdem-2006.pdf Implementing the Darcs Patch Formalism and Verifying It]) (see p. 11, 13--14.). The talk mentions also the notions of [[phantom type]], and [[existential type]], and [[type witness]] (see p. 15).<br />
<br />
== See also ==<br />
<br />
* [[Algebraic data type]]<br />
* [[GADTs for dummies]]<br />
* [http://en.wikibooks.org/wiki/Haskell/GADT The Haskell Wikibook section about GADT]<br />
* [http://apfelmus.nfshost.com/blog/2010/06/01-gadts-video.html A video that explains GADTs]<br />
<br />
<br />
[[Category:Glossary]]<br />
[[Category:Language extensions]]</div>
Steshaw
https://wiki.haskell.org/index.php?title=Applications_and_libraries/Compilers_and_interpreters&diff=63265
Applications and libraries/Compilers and interpreters
2020-03-10T07:27:41Z
<p>Steshaw: /* Lambda calculus */ reword</p>
<hr />
<div>Haskell, with its support for pattern matching on data structures,<br />
generic structure traversals, and expressive type system, is popular for<br />
implementing compilers and interpreters. Here's a selection of compilers<br />
and interpreters implemented in Haskell.<br />
<br />
==Large languages==<br />
<br />
===Haskell===<br />
<br />
;[http://haskell.org/ghc GHC]<br />
:GHC, The Glasgow Haskell Compiler, is written in Haskell<br />
<br />
;[[Yhc]]<br />
:Yhc, The York Haskell Compiler, is written in Haskell<br />
<br />
;[http://repetae.net/computer/jhc/ Jhc]<br />
:Jhc is a Haskell compiler which aims to produce the most efficient programs possible via whole program analysis<br />
<br />
;[http://haskell.org/nhc98 nhc98]<br />
:A compiler for Haskell 98, written in Haskell<br />
<br />
;[http://www.cs.uu.nl/groups/ST/Ehc/WebHome Ehc]<br />
:The purpose of the EHC project is to provide a description of a Haskell compiler which is as understandable as possible so it can be used for education as well as research.<br />
<br />
;[http://www.cs.uu.nl/wiki/UHC UHC]<br />
:UHC is the Utrecht Haskell Compiler. UHC supports almost all Haskell 98 features plus experimental extensions. The compiler runs under Mac OS X, Windows (Cygwin), and various Unix flavors.<br />
<br />
;[http://www.csg.lcs.mit.edu/projects/languages/ph.shtml pH]<br />
:A parallel version of Haskell from MIT.<br />
<br />
<br />
====Helium====<br />
<br />
;[http://www.cs.uu.nl/helium/ Helium]<br />
:A Haskell subset for educational purposes<br />
<br />
<br />
====Generic Haskell====<br />
<br />
;[http://generic-haskell.org/ Generic Haskell]<br />
:An extension of Haskell that supports generic programming<br />
<br />
<br />
====Data Field Haskell====<br />
<br />
;[http://www.mrtc.mdh.se/projects/DFH/ Data Field Haskell]<br />
:A dialect of the functional programming language Haskell that provides an instance of data fields<br />
<br />
<br />
====Eden====<br />
<br />
;[http://www.mathematik.uni-marburg.de/~eden/ Eden]<br />
:A Haskell dialect for parallel programming<br />
<br />
<br />
====Chameleon====<br />
<br />
;[http://taichi.ddns.comp.nus.edu.sg/taichiwiki/ChameleonHomePage Chameleon]<br />
:A Haskell-style language which implements the ideas described in a ``A Theory of Overloading``<br />
<br />
<br />
====CHR (Constraint Handling Rules)====<br />
<br />
;[http://www.cs.mu.oz.au/~gjd/haskellchr/ Haskell CHR]<br />
:A concurrent committed-choice constraint logic programming language, implemented using GHC's software transactional memory. According to the site referenced by the above-mentioned link, "It also contains an implementation of WAM for Haskell, so Prolog-style terms with variables are now possible."<br />
<br />
;[http://www.cs.kuleuven.be/~dtai/projects/CHR/systems/stmchr-0.1.tar.gz STM-based CHR implementation, by Michael Stahl] (gzipped TAR file)<br />
<br />
;[http://taichi.ddns.comp.nus.edu.sg/taichiwiki/CCHR CCHR: STM-based CHR implementation by Lam and Sulzmann]<br />
:According to the site referenced by the above-mentioned link, "CCHR is an experimental concurrent implementation of Constraint Handling Rules, designed to exploit concurrency and parallelism explicitly. CCHR is implemented in Haskell, with software transactional memory to manage synchronization of multiple solver threads working on the same problem. Constraint Handling Rules (CHR) is a concurrent committed choice constraint logic programming language to describe transformations (rewritings) among multi-sets of constraints (atomic formulae). CHR naturally support concurrent programming. Conjunction of constraints can be regarded as interacting collections of multiple asynchronous agents or processes. Their interaction is specified via transformation rules which can be applied simultaneously if the transformation rules do not interfere. Hence, one would expect to run CHR faster by executing transformation rules in parallel on a multi-core machine architecture. CCHR exactly allows such concurrency while solving CHR problems and exhibits significant speed up in most problems when executed on multi-core systems."<br />
<br />
<br />
=== Elm ===<br />
<br />
;[http://elm-lang.org/ Elm]<br />
:The Elm programming language aims to make web development more pleasant. Elm is a type-safe, functional reactive language that compiles to HTML, CSS, and JavaScript. <br />
<br />
<br />
===BASIC===<br />
<br />
;[http://hackage.haskell.org/package/BASIC BASIC]<br />
:A simplified version of the original BASIC embedded in Haskell.<br />
<br />
<br />
===Liskell===<br />
<br />
;[http://web.archive.org/web/20120609122549/http://www.liskell.org/ Liskell]<br />
:Liskell is Haskell on the inside but looks like Lisp on the outside<br />
<br />
===Perl===<br />
<br />
;[http://pugscode.org Pugs]<br />
:Pugs is an implementation of Perl 6, written in Haskell. It aims to implement the full Perl6 specification.<br />
<br />
<br />
===Python===<br />
<br />
;[http://hackage.haskell.org/package/berp-0.0.1 Berp]<br />
:Berp is an implementation of Python 3 in Haskell.<br />
<br />
;[http://code.google.com/p/haspy/ haspy]<br />
:Haspy is an implementation of Python in Haskell<br />
<br />
<br />
===Ruby===<br />
<br />
;[http://raa.ruby-lang.org/project/rtype/ RType]<br />
:RType is a Ruby interpreter written in Haskell<br />
<br />
<br />
===Flapjax===<br />
;[http://www.flapjax-lang.org/ Flapjax]<br />
:Flapjax is a language for functional reactive programming of AJAX web applications, whose compiler ([http://www.flapjax-lang.org/download/flapjax-source.tar.gz source]) is written in Haskell.<br />
<br />
<br />
===Scheme===<br />
<br />
;[http://halogen.note.amherst.edu/~jdtang/scheme_in_48/tutorial/overview.html Write Yourself a Scheme in 48 Hours]<br />
:A small Scheme interpreter<br />
<br />
;[http://www.korgwal.com/haskeem/ A Scheme in Haskell]<br />
<br />
<br />
===Lisp===<br />
<br />
;[http://www.defmacro.org/ramblings/lisp-in-haskell.html A Lisp Interpreter In Haskell]<br />
:A small lisp interpreter written in Haskell<br />
<br />
<br />
=== Emacs Lisp ===<br />
<br />
;[http://www.codersbase.com/index.php/helisp Helisp]<br />
:The beginnings of an Emacs lisp compiler/interpreter.<br />
<br />
<br />
===Epigram===<br />
<br />
;[http://www.e-pig.org/ Epigram]<br />
:Epigram is a prototype dependently typed functional programming language<br />
<br />
<br />
===Curry===<br />
<br />
;[http://danae.uni-muenster.de/~lux/curry/ The M&uuml;nster Curry Compiler]<br />
:A native code compiler for the declarative multi-paradigm language Curry, written in Haskell<br />
<br />
<br />
===Bluespec===<br />
;[http://www.bluespec.com Bluespec]<br />
:A compiler for a hardware description language translating a Haskell-like (but with System Verilog syntax these days) language to Verilog.<br />
<br />
<br />
===Cayenne===<br />
<br />
;[http://www.augustsson.net/Darcs/Cayenne/html/ Cayenne]<br />
:A compiler for a Haskell-like language with dependent types.<br />
<br />
<br />
===Agda===<br />
<br />
;[http://wiki.portal.chalmers.se/agda/pmwiki.php Agda]<br />
:A Cayenne-like programming language and proof assistant.<br />
<br />
<br />
===PolyP===<br />
<br />
;[http://www.cs.chalmers.se/~patrikj/poly/polyp/ PolyP]<br />
:A polytypic programming language<br />
<br />
<br />
===Forth===<br />
<br />
;[http://feather.perl6.nl/~nothingmuch/harrorth/ Harrorth]<br />
:Harrorth, a Forth interpreter<br />
<br />
<br />
===Eiffel===<br />
<br />
;[http://eiffelsoftware.origo.ethz.ch/index.php/DynBindModelHaskell Dynamic binding in Eiffel]<br />
:A model of dynamic binding in ECMA Eiffel, in Haskell<br />
<br />
<br />
===Crouton===<br />
<br />
;[http://crouton.sourceforge.net/ Crouton]<br />
:Crouton is a small but fairly complete functional programming language for querying and transforming parsed manuscripts, such as the PPCME. It is intended as an alternative to Corpus Search, based on a different philosophy. It is written in (and largely based on) the very nice functional programming language Haskell using the Parsec library<br />
<br />
<br />
=== JavaScript ===<br />
<br />
;[http://www.haskell.org/haskellwiki/Libraries_and_tools/HJS HJS]<br />
:HJS is a JavaScript parser written in Haskell. Available from HackageDB.<br />
<br />
<br />
===TCL===<br />
<br />
;[http://code.google.com/p/hiccup/ Hiccup]<br />
:Hiccup is a minimalistic TCL interpreter. It tries to be relatively simple, relatively efficient, and mostly correct. <br />
<br />
<br />
===Smalltalk===<br />
<br />
;[http://code.google.com/p/hst/ hst]<br />
:HST is a Smalltalk implementation in Haskell. [http://lstephen.wordpress.com/2007/07/23/completing-the-spike/ See here for more information]<br />
<br />
<br />
=== Discus ===<br />
<br />
;[[Discus]]<br />
:Discus is an experimental dialect of Haskell which investigates static typing and program transformation in the presence of computational effects. <br />
<br />
<br />
=== Timber ===<br />
<br />
;[http://timber-lang.org/Timber Timber]<br />
:Timber is a modern language for building event-driven systems, based around the notion of reactive objects. It is also a purely functional language derived from Haskell, although with a strict evaluation semantics. The Timber compiler currently runs on Linux and MacOS X platforms, but uses gcc as its back-end so it should be easily portable to most POSIX-like environments.<br />
<br />
=== Ivory ===<br />
<br />
;[http://ivorylang.org/ Ivory]<br />
: The Ivory Language is an eDSL for safe systems programming. You can think of Ivory as a safer C, embedded in Haskell. [https://github.com/GaloisInc/ivory Github]<br />
<br />
==Small languages==<br />
<br />
===PureScript===<br />
;[http://www.purescript.org/ PureScript]<br />
:A small strongly typed programming language that compiles to JavaScript<br />
<br />
===Baskell===<br />
;[http://www.cs.mu.oz.au/~bjpop/code.html Baskell]<br />
:An interpreter for a small functional programming language. Supports strict and non-strict evaluation, and type inference. Useful for teaching purposes.<br />
<br />
===LambdaPi===<br />
<br />
;[http://www.informatik.uni-bonn.de/~loeh/LambdaPi.html LambdaPi]<br />
:LambdaPi, An Implementation of a Dependently Typed Lambda Calculus<br />
<br />
===Unlambda===<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/code/lambdabot/scripts/Unlambda.hs Unlambda.hs]<br />
:An implementation of Unlambda in Haskell<br />
<br />
===BF===<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/code/lambdabot/scripts/BF.hs BF.hs]<br />
:An implementation of BF in Haskell<br />
<br />
<br />
===Lambda calculus===<br />
<br />
;[http://programming.reddit.com/goto?id=qnir 4 lambda calculus implementations]<br />
:[http://www.augustsson.net/Darcs/Lambda/ With code], by Lennart Augustsson.<br />
:[https://github.com/steshaw/lennart-lambda archived code on GitHub]<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/code/lambdabot/Plugin/Lambda/ LMEngine]<br />
:An implementation of the untyped lambda calculus<br />
<br />
===QML, a functional quantum programming language===<br />
<br />
;[http://sneezy.cs.nott.ac.uk/QML/ QML: A Functional Quantum Programming Language] project<br />
:It is implemented in Haskell.<br />
<br />
:For online material on quantum computing in general, see [http://www.theory.caltech.edu/people/preskill/ph229/ Quantum Computation] course held by [http://www.theory.caltech.edu/people/preskill/index.html John Preskill].<br />
<br />
===HQL - HHM's Quantified Lambda===<br />
<br />
;[http://www.archive.moraldo.com.ar/index.php/Articles/HQLlanguage Hernan's Quantified Lambda]<br />
:a small functional language, whose expressions can involve the use of quantifier operators<br />
<br />
===Atom===<br />
;[http://funhdl.org/wiki/doku.php/atom Atom]<br />
:Atom is a small HDL that compiles conditional term rewriting systems down to Verilog RTL.<br />
<br />
===Feldspar ===<br />
<br />
;[http://hackage.haskell.org/package/feldspar-language Feldspar]<br />
:Feldspar (Functional Embedded Language for DSP and PARallelism) is an embedded DSL for describing digital signal processing algorithms developed at Ericsson.<br />
<br />
===AL (Assignment Language)===<br />
<br />
:It is used for teaching purposes in at the Technical University of Vienna.<br />
:An interpreter implemented in Haskell is described in [http://www.logic.at/staff/robinson/ali.ps ALI - an AL Interpreter implemented in Haskell] written by Peter Robinson.<br />
<br />
=== Whitespace ===<br />
;[http://compsoc.dur.ac.uk/whitespace/index.php Whitespace]<br />
:A language that uses whitespace characters as language elements and ignores all non-whitespace characters<br />
<br />
=== LIPL ===<br />
;[http://www.lipl.googlepages.com/index.html LIPL]<br />
:An interpreter for a tiny functional programming language. It features Hindley-Milner style type inference.<br />
<br />
=== Ministg ===<br />
;[http://www.haskell.org/haskellwiki/Ministg Ministg]<br />
:An interpreter for a high-level, small-step, operational semantics for the STG machine. Features execution tracing, rendered in HTML. Useful for studying the behaviour of the STG machine and experimenting with extensions to the machine. Also useful for studying program language implementation.<br />
<br />
=== Constantinople ===<br />
;[http://zzo38computer.cjb.net/prog/Constantinople.zip Constantinople]<br />
:A compiler for the Constantinople esolang. There are two datatypes, the list, and the bit, which can either be 0 or 1. Lists are infinite and lazily evaluated.<br />
<br />
== Embedded languages ==<br />
<br />
=== ForSyDe ===<br />
The ForSyDe (Formal System Design) methodology has been developed with the objective to move system-on-chip design to a higher level of abstraction. ForSyDe is implemented as a Haskell-embedded behavioral DSL.<br />
<br />
== Debuggers ==<br />
<br />
;[http://www.dsic.upv.es/users/elp/debussy Debussy]<br />
:A declarative debugger for OBJ-like languages<br />
<br />
;See also [[Debugging]].<br />
<br />
{{LibrariesPage}}</div>
Steshaw
https://wiki.haskell.org/index.php?title=Applications_and_libraries/Compilers_and_interpreters&diff=63264
Applications and libraries/Compilers and interpreters
2020-03-10T07:26:54Z
<p>Steshaw: /* Lambda calculus */ Added link to non-dead code repo on GitHub</p>
<hr />
<div>Haskell, with its support for pattern matching on data structures,<br />
generic structure traversals, and expressive type system, is popular for<br />
implementing compilers and interpreters. Here's a selection of compilers<br />
and interpreters implemented in Haskell.<br />
<br />
==Large languages==<br />
<br />
===Haskell===<br />
<br />
;[http://haskell.org/ghc GHC]<br />
:GHC, The Glasgow Haskell Compiler, is written in Haskell<br />
<br />
;[[Yhc]]<br />
:Yhc, The York Haskell Compiler, is written in Haskell<br />
<br />
;[http://repetae.net/computer/jhc/ Jhc]<br />
:Jhc is a Haskell compiler which aims to produce the most efficient programs possible via whole program analysis<br />
<br />
;[http://haskell.org/nhc98 nhc98]<br />
:A compiler for Haskell 98, written in Haskell<br />
<br />
;[http://www.cs.uu.nl/groups/ST/Ehc/WebHome Ehc]<br />
:The purpose of the EHC project is to provide a description of a Haskell compiler which is as understandable as possible so it can be used for education as well as research.<br />
<br />
;[http://www.cs.uu.nl/wiki/UHC UHC]<br />
:UHC is the Utrecht Haskell Compiler. UHC supports almost all Haskell 98 features plus experimental extensions. The compiler runs under Mac OS X, Windows (Cygwin), and various Unix flavors.<br />
<br />
;[http://www.csg.lcs.mit.edu/projects/languages/ph.shtml pH]<br />
:A parallel version of Haskell from MIT.<br />
<br />
<br />
====Helium====<br />
<br />
;[http://www.cs.uu.nl/helium/ Helium]<br />
:A Haskell subset for educational purposes<br />
<br />
<br />
====Generic Haskell====<br />
<br />
;[http://generic-haskell.org/ Generic Haskell]<br />
:An extension of Haskell that supports generic programming<br />
<br />
<br />
====Data Field Haskell====<br />
<br />
;[http://www.mrtc.mdh.se/projects/DFH/ Data Field Haskell]<br />
:A dialect of the functional programming language Haskell that provides an instance of data fields<br />
<br />
<br />
====Eden====<br />
<br />
;[http://www.mathematik.uni-marburg.de/~eden/ Eden]<br />
:A Haskell dialect for parallel programming<br />
<br />
<br />
====Chameleon====<br />
<br />
;[http://taichi.ddns.comp.nus.edu.sg/taichiwiki/ChameleonHomePage Chameleon]<br />
:A Haskell-style language which implements the ideas described in a ``A Theory of Overloading``<br />
<br />
<br />
====CHR (Constraint Handling Rules)====<br />
<br />
;[http://www.cs.mu.oz.au/~gjd/haskellchr/ Haskell CHR]<br />
:A concurrent committed-choice constraint logic programming language, implemented using GHC's software transactional memory. According to the site referenced by the above-mentioned link, "It also contains an implementation of WAM for Haskell, so Prolog-style terms with variables are now possible."<br />
<br />
;[http://www.cs.kuleuven.be/~dtai/projects/CHR/systems/stmchr-0.1.tar.gz STM-based CHR implementation, by Michael Stahl] (gzipped TAR file)<br />
<br />
;[http://taichi.ddns.comp.nus.edu.sg/taichiwiki/CCHR CCHR: STM-based CHR implementation by Lam and Sulzmann]<br />
:According to the site referenced by the above-mentioned link, "CCHR is an experimental concurrent implementation of Constraint Handling Rules, designed to exploit concurrency and parallelism explicitly. CCHR is implemented in Haskell, with software transactional memory to manage synchronization of multiple solver threads working on the same problem. Constraint Handling Rules (CHR) is a concurrent committed choice constraint logic programming language to describe transformations (rewritings) among multi-sets of constraints (atomic formulae). CHR naturally support concurrent programming. Conjunction of constraints can be regarded as interacting collections of multiple asynchronous agents or processes. Their interaction is specified via transformation rules which can be applied simultaneously if the transformation rules do not interfere. Hence, one would expect to run CHR faster by executing transformation rules in parallel on a multi-core machine architecture. CCHR exactly allows such concurrency while solving CHR problems and exhibits significant speed up in most problems when executed on multi-core systems."<br />
<br />
<br />
=== Elm ===<br />
<br />
;[http://elm-lang.org/ Elm]<br />
:The Elm programming language aims to make web development more pleasant. Elm is a type-safe, functional reactive language that compiles to HTML, CSS, and JavaScript. <br />
<br />
<br />
===BASIC===<br />
<br />
;[http://hackage.haskell.org/package/BASIC BASIC]<br />
:A simplified version of the original BASIC embedded in Haskell.<br />
<br />
<br />
===Liskell===<br />
<br />
;[http://web.archive.org/web/20120609122549/http://www.liskell.org/ Liskell]<br />
:Liskell is Haskell on the inside but looks like Lisp on the outside<br />
<br />
===Perl===<br />
<br />
;[http://pugscode.org Pugs]<br />
:Pugs is an implementation of Perl 6, written in Haskell. It aims to implement the full Perl6 specification.<br />
<br />
<br />
===Python===<br />
<br />
;[http://hackage.haskell.org/package/berp-0.0.1 Berp]<br />
:Berp is an implementation of Python 3 in Haskell.<br />
<br />
;[http://code.google.com/p/haspy/ haspy]<br />
:Haspy is an implementation of Python in Haskell<br />
<br />
<br />
===Ruby===<br />
<br />
;[http://raa.ruby-lang.org/project/rtype/ RType]<br />
:RType is a Ruby interpreter written in Haskell<br />
<br />
<br />
===Flapjax===<br />
;[http://www.flapjax-lang.org/ Flapjax]<br />
:Flapjax is a language for functional reactive programming of AJAX web applications, whose compiler ([http://www.flapjax-lang.org/download/flapjax-source.tar.gz source]) is written in Haskell.<br />
<br />
<br />
===Scheme===<br />
<br />
;[http://halogen.note.amherst.edu/~jdtang/scheme_in_48/tutorial/overview.html Write Yourself a Scheme in 48 Hours]<br />
:A small Scheme interpreter<br />
<br />
;[http://www.korgwal.com/haskeem/ A Scheme in Haskell]<br />
<br />
<br />
===Lisp===<br />
<br />
;[http://www.defmacro.org/ramblings/lisp-in-haskell.html A Lisp Interpreter In Haskell]<br />
:A small lisp interpreter written in Haskell<br />
<br />
<br />
=== Emacs Lisp ===<br />
<br />
;[http://www.codersbase.com/index.php/helisp Helisp]<br />
:The beginnings of an Emacs lisp compiler/interpreter.<br />
<br />
<br />
===Epigram===<br />
<br />
;[http://www.e-pig.org/ Epigram]<br />
:Epigram is a prototype dependently typed functional programming language<br />
<br />
<br />
===Curry===<br />
<br />
;[http://danae.uni-muenster.de/~lux/curry/ The M&uuml;nster Curry Compiler]<br />
:A native code compiler for the declarative multi-paradigm language Curry, written in Haskell<br />
<br />
<br />
===Bluespec===<br />
;[http://www.bluespec.com Bluespec]<br />
:A compiler for a hardware description language translating a Haskell-like (but with System Verilog syntax these days) language to Verilog.<br />
<br />
<br />
===Cayenne===<br />
<br />
;[http://www.augustsson.net/Darcs/Cayenne/html/ Cayenne]<br />
:A compiler for a Haskell-like language with dependent types.<br />
<br />
<br />
===Agda===<br />
<br />
;[http://wiki.portal.chalmers.se/agda/pmwiki.php Agda]<br />
:A Cayenne-like programming language and proof assistant.<br />
<br />
<br />
===PolyP===<br />
<br />
;[http://www.cs.chalmers.se/~patrikj/poly/polyp/ PolyP]<br />
:A polytypic programming language<br />
<br />
<br />
===Forth===<br />
<br />
;[http://feather.perl6.nl/~nothingmuch/harrorth/ Harrorth]<br />
:Harrorth, a Forth interpreter<br />
<br />
<br />
===Eiffel===<br />
<br />
;[http://eiffelsoftware.origo.ethz.ch/index.php/DynBindModelHaskell Dynamic binding in Eiffel]<br />
:A model of dynamic binding in ECMA Eiffel, in Haskell<br />
<br />
<br />
===Crouton===<br />
<br />
;[http://crouton.sourceforge.net/ Crouton]<br />
:Crouton is a small but fairly complete functional programming language for querying and transforming parsed manuscripts, such as the PPCME. It is intended as an alternative to Corpus Search, based on a different philosophy. It is written in (and largely based on) the very nice functional programming language Haskell using the Parsec library<br />
<br />
<br />
=== JavaScript ===<br />
<br />
;[http://www.haskell.org/haskellwiki/Libraries_and_tools/HJS HJS]<br />
:HJS is a JavaScript parser written in Haskell. Available from HackageDB.<br />
<br />
<br />
===TCL===<br />
<br />
;[http://code.google.com/p/hiccup/ Hiccup]<br />
:Hiccup is a minimalistic TCL interpreter. It tries to be relatively simple, relatively efficient, and mostly correct. <br />
<br />
<br />
===Smalltalk===<br />
<br />
;[http://code.google.com/p/hst/ hst]<br />
:HST is a Smalltalk implementation in Haskell. [http://lstephen.wordpress.com/2007/07/23/completing-the-spike/ See here for more information]<br />
<br />
<br />
=== Discus ===<br />
<br />
;[[Discus]]<br />
:Discus is an experimental dialect of Haskell which investigates static typing and program transformation in the presence of computational effects. <br />
<br />
<br />
=== Timber ===<br />
<br />
;[http://timber-lang.org/Timber Timber]<br />
:Timber is a modern language for building event-driven systems, based around the notion of reactive objects. It is also a purely functional language derived from Haskell, although with a strict evaluation semantics. The Timber compiler currently runs on Linux and MacOS X platforms, but uses gcc as its back-end so it should be easily portable to most POSIX-like environments.<br />
<br />
=== Ivory ===<br />
<br />
;[http://ivorylang.org/ Ivory]<br />
: The Ivory Language is an eDSL for safe systems programming. You can think of Ivory as a safer C, embedded in Haskell. [https://github.com/GaloisInc/ivory Github]<br />
<br />
==Small languages==<br />
<br />
===PureScript===<br />
;[http://www.purescript.org/ PureScript]<br />
:A small strongly typed programming language that compiles to JavaScript<br />
<br />
===Baskell===<br />
;[http://www.cs.mu.oz.au/~bjpop/code.html Baskell]<br />
:An interpreter for a small functional programming language. Supports strict and non-strict evaluation, and type inference. Useful for teaching purposes.<br />
<br />
===LambdaPi===<br />
<br />
;[http://www.informatik.uni-bonn.de/~loeh/LambdaPi.html LambdaPi]<br />
:LambdaPi, An Implementation of a Dependently Typed Lambda Calculus<br />
<br />
===Unlambda===<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/code/lambdabot/scripts/Unlambda.hs Unlambda.hs]<br />
:An implementation of Unlambda in Haskell<br />
<br />
===BF===<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/code/lambdabot/scripts/BF.hs BF.hs]<br />
:An implementation of BF in Haskell<br />
<br />
<br />
===Lambda calculus===<br />
<br />
;[http://programming.reddit.com/goto?id=qnir 4 lambda calculus implementations]<br />
:[http://www.augustsson.net/Darcs/Lambda/ With code], by Lennart Augustsson.<br />
:[https://github.com/steshaw/lennart-lambda copy of code in GitHub]<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/code/lambdabot/Plugin/Lambda/ LMEngine]<br />
:An implementation of the untyped lambda calculus<br />
<br />
===QML, a functional quantum programming language===<br />
<br />
;[http://sneezy.cs.nott.ac.uk/QML/ QML: A Functional Quantum Programming Language] project<br />
:It is implemented in Haskell.<br />
<br />
:For online material on quantum computing in general, see [http://www.theory.caltech.edu/people/preskill/ph229/ Quantum Computation] course held by [http://www.theory.caltech.edu/people/preskill/index.html John Preskill].<br />
<br />
===HQL - HHM's Quantified Lambda===<br />
<br />
;[http://www.archive.moraldo.com.ar/index.php/Articles/HQLlanguage Hernan's Quantified Lambda]<br />
:a small functional language, whose expressions can involve the use of quantifier operators<br />
<br />
===Atom===<br />
;[http://funhdl.org/wiki/doku.php/atom Atom]<br />
:Atom is a small HDL that compiles conditional term rewriting systems down to Verilog RTL.<br />
<br />
===Feldspar ===<br />
<br />
;[http://hackage.haskell.org/package/feldspar-language Feldspar]<br />
:Feldspar (Functional Embedded Language for DSP and PARallelism) is an embedded DSL for describing digital signal processing algorithms developed at Ericsson.<br />
<br />
===AL (Assignment Language)===<br />
<br />
:It is used for teaching purposes in at the Technical University of Vienna.<br />
:An interpreter implemented in Haskell is described in [http://www.logic.at/staff/robinson/ali.ps ALI - an AL Interpreter implemented in Haskell] written by Peter Robinson.<br />
<br />
=== Whitespace ===<br />
;[http://compsoc.dur.ac.uk/whitespace/index.php Whitespace]<br />
:A language that uses whitespace characters as language elements and ignores all non-whitespace characters<br />
<br />
=== LIPL ===<br />
;[http://www.lipl.googlepages.com/index.html LIPL]<br />
:An interpreter for a tiny functional programming language. It features Hindley-Milner style type inference.<br />
<br />
=== Ministg ===<br />
;[http://www.haskell.org/haskellwiki/Ministg Ministg]<br />
:An interpreter for a high-level, small-step, operational semantics for the STG machine. Features execution tracing, rendered in HTML. Useful for studying the behaviour of the STG machine and experimenting with extensions to the machine. Also useful for studying program language implementation.<br />
<br />
=== Constantinople ===<br />
;[http://zzo38computer.cjb.net/prog/Constantinople.zip Constantinople]<br />
:A compiler for the Constantinople esolang. There are two datatypes, the list, and the bit, which can either be 0 or 1. Lists are infinite and lazily evaluated.<br />
<br />
== Embedded languages ==<br />
<br />
=== ForSyDe ===<br />
The ForSyDe (Formal System Design) methodology has been developed with the objective to move system-on-chip design to a higher level of abstraction. ForSyDe is implemented as a Haskell-embedded behavioral DSL.<br />
<br />
== Debuggers ==<br />
<br />
;[http://www.dsic.upv.es/users/elp/debussy Debussy]<br />
:A declarative debugger for OBJ-like languages<br />
<br />
;See also [[Debugging]].<br />
<br />
{{LibrariesPage}}</div>
Steshaw
https://wiki.haskell.org/index.php?title=Consultants&diff=62953
Consultants
2019-07-02T00:42:33Z
<p>Steshaw: /* Australasia */ Tweak steshaw's contact details</p>
<hr />
<div>== Australasia ==<br />
; Ben Lippmeier http://benl.ouroborus.net<br />
: [mailto:benl@ouroborus.net benl@ouroborus.net]<br />
: Sydney, Australia.<br />
<br />
; Steven Shaw https://steshaw.org<br />
: [mailto:steven@steshaw.org steven@steshaw.org]<br />
: Brisbane, Australia.<br />
<br />
== Europe ==<br />
; Clockwork Consulting ApS https://www.cwconsult.dk/<br />
: [mailto:info@cwconsult.dk info@cwconsult.dk]<br />
: Copenhagen, Denmark. Remote work only (unless in Copenhagen, ask if so).<br />
<br />
; NilCons http://www.nilcons.com/<br />
: [mailto:cons@nilcons.com cons@nilcons.com]<br />
: Zurich, Switzerland.<br />
<br />
; Tweag I/O http://tweag.io/<br />
: [mailto:hello@tweag.io hello@tweag.io]<br />
: Europe, US, Russia, South America. Headquartered in Paris, France.<br />
<br />
; Monadfix https://monadfix.com<br />
: We help companies adopt functional programming (Haskell, Agda, PureScript, Clojure)<br />
: [mailto:hi@monadfix.com hi@monadfix.com]<br />
: Europe and Russia, remote work worldwide.<br />
<br />
; Well-Typed LLP http://www.well-typed.com/<br />
: The Haskell Consultants<br />
: [mailto:info@well-typed.com info@well-typed.com]<br />
: Europe and US on-site, remote work worldwide.<br />
<br />
; zerobuzz UG https://zerobuzz.net/<br />
: [mailto:info@zerobuzz.net info@zerobuzz.net]<br />
: Germany and Switzerland<br />
<br />
; Turing Jump https://turingjump.com/<br />
: [mailto:info@turingjump.com info@turingjump.com]<br />
: Europe on-site, remote work worldwide.<br />
<br />
== North-America ==<br />
; AppSolutions LLC http://www.appsolutions.com/<br />
: Anton van Straaten http://www.appsolutions.com/anton/<br />
: New York, Boston, Philadelphia, Washington DC<br />
<br />
; Boltmade http://boltmade.com<br />
: Waterloo, ON, Canada<br />
<br />
; Brett Letner http://www.linkedin.com/in/brettletner<br />
: Lawrence, KS, USA<br />
<br />
; Civic Labs [https://www.civiclabs.com https://www.civiclabs.com]<br />
: New York, NY and San Francisco, CA<br />
<br />
; LambdaPix http://lambdapix.com<br />
: Conal Elliott<br />
: Blog: http://conal.net/blog<br />
: San Andreas, CA, USA<br />
<br />
; Obsidian Systems [https://obsidian.systems https://obsidian.systems]<br />
: New York, NY<br />
<br />
; OM Consulting Limited ''[mailto:omconsult@gmail.com omconsult@gmail.com]'' :Intelligent solutions.<br />
<br />
; Pliosoft Corp. [https://pliosoft.com/ https://pliosoft.com/] <br />
: email ''[mailto:contact@pliosoft.com contact@pliosoft.com]'' <br />
: Haskell consulting and development<br />
: Alberta, Canada<br />
<br />
; Position Development [http://positiondev.com http://positiondev.com]<br />
: New York, NY<br />
<br />
; Sankel Software http://sankelsoftware.com<br />
: David Sankel<br />
: Albuquerque, NM, USA<br />
<br />
; Simon Michael http://joyful.com<br />
: Los Angeles<br />
<br />
; Stack Builders http://www.stackbuilders.com<br />
: New York, NY, USA<br />
<br />
== Asia ==<br />
; ByteAlly Software http://www.byteally.com/<br />
: Chennai, India<br />
<br />
[[Category:Community]]</div>
Steshaw
https://wiki.haskell.org/index.php?title=User:Steshaw&diff=62952
User:Steshaw
2019-07-02T00:42:13Z
<p>Steshaw: Make link https</p>
<hr />
<div>Steven Shaw loves programming languages!<br />
<br />
[https://steshaw.org/ steshaw.org]<br />
[http://twitter.com/steshaw @steshaw]</div>
Steshaw
https://wiki.haskell.org/index.php?title=Applications_and_libraries/Theorem_provers&diff=62510
Applications and libraries/Theorem provers
2018-06-13T04:25:41Z
<p>Steshaw: /* Applications */ Correct capitalisation</p>
<hr />
<div>Tools for formal reasoning, written in Haskell.<br />
<br />
== Applications ==<br />
<br />
;[http://wiki.portal.chalmers.se/agda/agda.php Agda] <br />
:Agda is a system for incrementally developing proofs and programs. Agda is also a functional language with [[Dependent type]]s. This language is very similar to Cayenne and Agda is intended to be a (almost) full implementation of it in the future.<br />
<br />
;[http://citeseer.ist.psu.edu/29367.html A resolution-based theorem prover for FOL]<br />
:Haskell implementation of a resolution based theorem prover for first order logic.<br />
<br />
;[http://www-ps.iai.uni-bonn.de/cgi-bin/free-theorems-webui.cgi Automatic generation of free theorems]<br />
:Web interface for generating theorems from Haskell types.<br />
<br />
;[http://wiki.di.uminho.pt/wiki/bin/view/PURe/Camila Camila]<br />
:Camila is a system for software development using formal methods. Other materials on formal methods can be found also on the [[Analysis and design|analysis and design]] page.<br />
<br />
;[http://www.augustsson.net/Darcs/Cayenne/html/ Cayenne]<br />
:Cayenne is a functional language with a powerful [[Dependent type|dependent type system]]. The basic types are functions, products, and sums. Functions and products use dependent types to gain additional power. As with Epigram, a dependently typed language may be used to encode strong proofs in the type system. The language is no longer supportd; the link points to a page stored in the Web Archive.<br />
<br />
;[http://www.lix.polytechnique.fr/dedukti Dedukti]<br />
:Dedukti is a proof checker for the λΠ-modulo calculus, a dependently typed λ-calculus with the addition of typed rewrite rules, capable of expressing proofs in Deduction Modulo.<br />
<br />
;[http://www.cwi.nl/~jve/demo/ DEMO]<br />
:Model checking for dynamic epistemic logic. DEMO is a tool for modelling change in epistemic logic (the logic of knowledge). Among other things, DEMO allows modeling epistemic updates, graphical display of update results, graphical display of action models, formula evaluation in epistemic models, translation of dynamic epistemic formulas to PDL (propositional dynamic logic) formulas. More materials and other Haskell resources on dynamic epistemic modelling (and more generally on logic and [[linguistics]]) can be found on [http://homepages.cwi.nl/~jve/index.html Jan van Eijck's page].<br />
;[http://darcs.augustsson.net/Darcs/Djinn Djinn]<br />
:Djinn generates Haskell code from a type declaration, using a decision procedure from intuitionistic propositional calculus.<br />
<br />
;[http://www.haskell.org/dumatel/ Dumatel] <br />
: Dumatel is a prover based on many-sorted term rewriting (TRW) and equational reasoning<br />
<br />
;Epigram<br />
:Epigram is a prototype [[Dependent type|dependently typed]] functional programming language, equipped with an interactive editing and typechecking environment. High-level Epigram source code elaborates into a dependent type theory based on Zhaohui Luo's UTT. Programming with evidence lies at the heart of Epigram's design.<br />
<br />
;[http://www.cs.chalmers.se/~koen/folkung/ Equinox]<br />
:Equinox is a new theorem prover for pure first-order logic with equality. It finds ground proofs of the input theory, by solving successive ground instantiations of the theory using an incremental SAT-solver. Equality is dealt with using a Nelson-Oppen framework.<br />
<br />
;[http://fldit-www.cs.uni-dortmund.de/~peter/ExpNeu/Welcome.html Expander2]<br />
:Expander2 is a flexible multi-purpose workbench for rewriting, verification, constraint solving, flow graph analysis and related procedures that build up proofs or computation sequences. Moreover, tailor-made interpreters display terms as 2D structures ranging from trees and rooted graphs to tables, fractals and other turtle-system-generated pictures.<br />
<br />
;[http://www.cs.yale.edu/homes/cc392/report.html FOL Resolution Theorem Prover]<br />
:An implementation of a simple theorem prover in first-order logic using Haskell.<br />
<br />
;[http://taz.cs.wcupa.edu/~dmead/code/prover/ Halp]<br />
:Haskell Logic Prover is written in Haskell supports first order logic with plans to add predicates. Also included is a simple frontend written with gtk2hs<br />
<br />
;[http://isabelle.in.tum.de/haskabelle.html Haskabelle]<br />
:Haskabelle is a converter from Haskell source files to Isabelle/HOL theories implemented in Haskell itself<br />
<br />
;[http://www.informatik.uni-bremen.de/agbkb/forschung/formal_methods/CoFI/hets/ Hets]<br />
:The Heterogeneous Tool Set (Hets) is a parsing, static analysis and proof management tool combining various tools for different specification languages, thus providing a tool for heterogeneous specifications. It supports HasCASL for specification of Haskell programs, and uses Isabelle for proving<br />
<br />
;[http://www.math.chalmers.se/~koen/paradox/ Paradox]<br />
:Paradox processes first-order logic problems and tries to find finite-domain models for them.<br />
<br />
;[http://proofgeneral.inf.ed.ac.uk/Kit Proof General Kit]<br />
:The Proof General Kit designs and implements a component-based framework for interactive theorem proving. The central middleware of the toolkit is implemented in Haskell. The project is the sucessor of the highly successful Emacs-based Proof General interface.<br />
<br />
;[http://www.haskell.org/yarrow/ Yarrow]<br />
:Yarrow is a proof-assistant for Pure Type Systems (PTSs) with several extensions. In Yarrow you can experiment with various pure type systems, representing different logics and programming languages.<br />
<br />
;[[Zeno]]<br />
:Zeno is an automated proof system for Haskell program properties; developed at Imperial College London by William Sonnex, Sophia Drossopoulou and Susan Eisenbach. It aims to solve the general problem of equality between two Haskell terms, for any input value. Proofs and programs are output as [http://www.cl.cam.ac.uk/research/hvg/Isabelle/ Isabelle/HOL] theories which are then automatically verified by said tool.<br />
<br />
== Libraries ==<br />
<br />
;[http://eb.host.cs.st-andrews.ac.uk/ivor.php Ivor]<br />
:is a type theory based theorem proving library -- written by [https://edwinb.wordpress.com/ Edwin Brady] (see also the author's homepage, there are a lot of materials concerning [[dependent type]] theory there).<br />
<br />
{{LibrariesPage}}</div>
Steshaw
https://wiki.haskell.org/index.php?title=Consultants&diff=62411
Consultants
2018-04-09T21:14:23Z
<p>Steshaw: /* Australasia */ Added TLC SRC</p>
<hr />
<div>== Australasia ==<br />
; Ben Lippmeier http://benl.ouroborus.net<br />
: [mailto:benl@ouroborus.net benl@ouroborus.net]<br />
: Sydney, Australia.<br />
<br />
; TLC SRC http://tlcsrc.ml<br />
: Steven Shaw<br />
: Blog: http://steshaw.org<br />
: [mailto:steven@steshaw.org steven@steshaw.org]<br />
: Brisbane, Australia.<br />
<br />
== Europe ==<br />
; Clockwork Consulting ApS https://www.cwconsult.dk/<br />
: [mailto:info@cwconsult.dk info@cwconsult.dk]<br />
: Copenhagen, Denmark. Remote work only (unless in Copenhagen, ask if so).<br />
<br />
; NilCons http://www.nilcons.com/<br />
: [mailto:cons@nilcons.com cons@nilcons.com]<br />
: Zurich, Switzerland.<br />
<br />
; Tweag I/O http://tweag.io/<br />
: [mailto:hello@tweag.io hello@tweag.io]<br />
: Europe, US, Russia, South America. Headquartered in Paris, France.<br />
<br />
; Well-Typed LLP http://www.well-typed.com/<br />
: The Haskell Consultants<br />
: [mailto:info@well-typed.com info@well-typed.com]<br />
: Europe and US on-site, remote work worldwide.<br />
<br />
; zerobuzz UG https://zerobuzz.net/<br />
: [mailto:info@zerobuzz.net info@zerobuzz.net]<br />
: Germany and Switzerland<br />
<br />
; Turing Jump https://turingjump.com/<br />
: [mailto:info@turingjump.com info@turingjump.com]<br />
: Europe on-site, remote work worldwide.<br />
<br />
== North-America ==<br />
; AppSolutions LLC http://www.appsolutions.com/<br />
: Anton van Straaten http://www.appsolutions.com/anton/<br />
: New York, Boston, Philadelphia, Washington DC<br />
<br />
; Boltmade http://boltmade.com<br />
: Waterloo, ON, Canada<br />
<br />
; Brett Letner http://www.linkedin.com/in/brettletner<br />
: Lawrence, KS, USA<br />
<br />
; Chris Forno [http://jekor.com/ http://jekor.com/]<br />
: San Francisco<br />
<br />
; Civic Labs [https://www.civiclabs.com https://www.civiclabs.com]<br />
: New York, NY and San Francisco, CA<br />
<br />
; LambdaPix http://lambdapix.com<br />
: Conal Elliott<br />
: Blog: http://conal.net/blog<br />
: San Andreas, CA, USA<br />
<br />
; Obsidian Systems [https://obsidian.systems https://obsidian.systems]<br />
: New York, NY<br />
<br />
; OM Consulting Limited ''[mailto:omconsult@gmail.com omconsult@gmail.com]'' :Intelligent solutions.<br />
<br />
; Pliosoft Corp. [https://pliosoft.com/ https://pliosoft.com/] <br />
: email ''[mailto:contact@pliosoft.com contact@pliosoft.com]'' <br />
: Haskell consulting and development<br />
: Alberta, Canada<br />
<br />
; Position Development [http://positiondev.com http://positiondev.com]<br />
: New York, NY<br />
<br />
; Reichert Brothers [http://reichertbrothers.com/ http://reichertbrothers.com/]<br />
: Haskell Consulting, Training, and Mentoring<br />
: ''[mailto:info@reichertbrothers.com info@reichertbrothers.com]''<br />
: Houston, Texas, USA<br />
<br />
; Sankel Software http://sankelsoftware.com<br />
: David Sankel<br />
: Albuquerque, NM, USA<br />
<br />
; Simon Michael http://joyful.com<br />
: Los Angeles<br />
<br />
; Stack Builders http://www.stackbuilders.com<br />
: New York, NY, USA<br />
<br />
== Asia ==<br />
; ByteAlly Software http://www.byteally.com/<br />
: Chennai, India<br />
<br />
[[Category:Community]]</div>
Steshaw
https://wiki.haskell.org/index.php?title=Consultants&diff=62410
Consultants
2018-04-09T21:12:08Z
<p>Steshaw: /* Australasia */ Added Steven Shaw</p>
<hr />
<div>== Australasia ==<br />
; Ben Lippmeier http://benl.ouroborus.net<br />
: [mailto:benl@ouroborus.net benl@ouroborus.net]<br />
: Sydney, Australia.<br />
<br />
; Steven Shaw http://steshaw.org<br />
: [mailto:steven@steshaw.org steven@steshaw.org]<br />
: Brisbane, Australia.<br />
<br />
== Europe ==<br />
; Clockwork Consulting ApS https://www.cwconsult.dk/<br />
: [mailto:info@cwconsult.dk info@cwconsult.dk]<br />
: Copenhagen, Denmark. Remote work only (unless in Copenhagen, ask if so).<br />
<br />
; NilCons http://www.nilcons.com/<br />
: [mailto:cons@nilcons.com cons@nilcons.com]<br />
: Zurich, Switzerland.<br />
<br />
; Tweag I/O http://tweag.io/<br />
: [mailto:hello@tweag.io hello@tweag.io]<br />
: Europe, US, Russia, South America. Headquartered in Paris, France.<br />
<br />
; Well-Typed LLP http://www.well-typed.com/<br />
: The Haskell Consultants<br />
: [mailto:info@well-typed.com info@well-typed.com]<br />
: Europe and US on-site, remote work worldwide.<br />
<br />
; zerobuzz UG https://zerobuzz.net/<br />
: [mailto:info@zerobuzz.net info@zerobuzz.net]<br />
: Germany and Switzerland<br />
<br />
; Turing Jump https://turingjump.com/<br />
: [mailto:info@turingjump.com info@turingjump.com]<br />
: Europe on-site, remote work worldwide.<br />
<br />
== North-America ==<br />
; AppSolutions LLC http://www.appsolutions.com/<br />
: Anton van Straaten http://www.appsolutions.com/anton/<br />
: New York, Boston, Philadelphia, Washington DC<br />
<br />
; Boltmade http://boltmade.com<br />
: Waterloo, ON, Canada<br />
<br />
; Brett Letner http://www.linkedin.com/in/brettletner<br />
: Lawrence, KS, USA<br />
<br />
; Chris Forno [http://jekor.com/ http://jekor.com/]<br />
: San Francisco<br />
<br />
; Civic Labs [https://www.civiclabs.com https://www.civiclabs.com]<br />
: New York, NY and San Francisco, CA<br />
<br />
; LambdaPix http://lambdapix.com<br />
: Conal Elliott<br />
: Blog: http://conal.net/blog<br />
: San Andreas, CA, USA<br />
<br />
; Obsidian Systems [https://obsidian.systems https://obsidian.systems]<br />
: New York, NY<br />
<br />
; OM Consulting Limited ''[mailto:omconsult@gmail.com omconsult@gmail.com]'' :Intelligent solutions.<br />
<br />
; Pliosoft Corp. [https://pliosoft.com/ https://pliosoft.com/] <br />
: email ''[mailto:contact@pliosoft.com contact@pliosoft.com]'' <br />
: Haskell consulting and development<br />
: Alberta, Canada<br />
<br />
; Position Development [http://positiondev.com http://positiondev.com]<br />
: New York, NY<br />
<br />
; Reichert Brothers [http://reichertbrothers.com/ http://reichertbrothers.com/]<br />
: Haskell Consulting, Training, and Mentoring<br />
: ''[mailto:info@reichertbrothers.com info@reichertbrothers.com]''<br />
: Houston, Texas, USA<br />
<br />
; Sankel Software http://sankelsoftware.com<br />
: David Sankel<br />
: Albuquerque, NM, USA<br />
<br />
; Simon Michael http://joyful.com<br />
: Los Angeles<br />
<br />
; Stack Builders http://www.stackbuilders.com<br />
: New York, NY, USA<br />
<br />
== Asia ==<br />
; ByteAlly Software http://www.byteally.com/<br />
: Chennai, India<br />
<br />
[[Category:Community]]</div>
Steshaw
https://wiki.haskell.org/index.php?title=User:Steshaw&diff=61122
User:Steshaw
2016-09-18T06:03:57Z
<p>Steshaw: </p>
<hr />
<div>Steven Shaw loves programming languages!<br />
<br />
[http://steshaw.org/ steshaw.org]<br />
[http://twitter.com/steshaw @steshaw]</div>
Steshaw
https://wiki.haskell.org/index.php?title=The_JavaScript_Problem&diff=57916
The JavaScript Problem
2014-04-21T04:36:42Z
<p>Steshaw: /* GorrilaScript */ correct spelling</p>
<hr />
<div>== The problem ==<br />
<br />
The JavaScript problem is two-fold and can be described thus:<br />
<br />
# '''JavaScript sucks.''' The depths to which JavaScript sucks is well-documented and well-understood. Its main faults are: its lack of module system, weak-typing, verbose function syntax¹, late binding², which has led to the creation of various static analysis tools to alleviate this language flaw³, but with limited success⁴ (there is even a static type checker⁵), finicky equality/automatic conversion, <code>this</code> behaviour, and lack of static types.<br />
<br />
# '''We need JavaScript.''' Using it for what it is good for, i.e. providing a platform for browser development, but not using the language ''per se'', is therefore desirable, and many are working to achieve this, in varying forms. There are various ways to do it, but we ought to opt for compiling an existing language, Haskell, to JavaScript, because we do not have time to learn or teach other people a new language, garner a new library set and a new type checker and all that Haskell implementations provide.<br />
<br />
== Mainstream alternatives ==<br />
<br />
=== Coffeescript ===<br />
It makes many aspects of Javascript sane and convenient, and you get a compilation check that verifies syntax, however it still suffers greatly from weak-typing.<br />
<br />
=== TypeScript ===<br />
<br />
Structural typing with traditional generics on top of Javascript.<br />
Of all the alternatvies, TypeScript's advantage is that it makes no changes to Javascript. Existing javascript code that passes jshint is valid Typescript code. TypeScript also adds features from the latest javascript standards that it can compile down to older versions of javascript. TypeScript is by far the easiest javascript variant to learn. The downside is that one might desire a better language then just javascript + types.<br />
<br />
TypeScript defaults to dynamic typing when it can't figure the type out. However, it now has a noImplicitAny setting that will give a compilation error if it can't figure out the type.<br />
<br />
Structural sub-typing seems a good fit for JavaScript. <br />
Perhaps Typescript's biggest problem is that null is a valid value for any type.<br />
<br />
== Haskell -> JS ==<br />
<br />
=== UHC ===<br />
<br />
Original blog post [https://github.com/atzedijkstra/javascript-runtime-for-UHC here.] Quickstart guide [http://chrisdone.com/posts/2012-01-06-uhc-javascript.html here.] A more in-depth discussion about the current capabilities of the backend [http://www.norm2782.com/improving-uhc-js-report.pdf here.] For an example of using the JavaScript compilation for a real app see this [http://alessandrovermeulen.me/2012/01/26/getting-rid-of-javascript-with-haskell/ blog post], there is also a port of wxAsteroids to the browser (see [http://uu-computerscience.github.io/js-asteroids/ github] or a [http://www.rubendegooijer.nl/posts/2013-04-06-haskell-oop.html blog post]). <br />
<br />
* Beta.<br />
* Only works for UHC, but promising. <br />
* UHC compiles enough of Hackage to be very useful.<br />
* Doesn't produce an explosion of code, seemingly.<br />
* Fairly substantial JS/DOM/W3C/HTML5 API.<br />
* Currently works.<br />
<br />
=== Fay ===<br />
<br />
Website: http://fay-lang.org/ Discussion on Reddit: [http://www.reddit.com/r/haskell/comments/11yrpi/fay_slides/ Fay slides]. The package is on [http://hackage.haskell.org/package/fay Hackage]. Fetch with Git: <br />
git clone git://github.com/faylang/fay.git<br />
<br />
* Compiles a subset of Haskell, needs more<br />
* Currently works.<br />
<br />
=== GHCJS ===<br />
<br />
The Github page is [https://github.com/ghcjs/ghcjs here.]<br />
<br />
* Alpha.<br />
* Works.<br />
* Incomplete.<br />
* Nicely designed.<br />
* Compiles most pure Haskell libraries no problem.<br />
* FFI to JS works, and the author, sviperll is a helpful guy.<br />
<br />
=== Haste ===<br />
<br />
[http://haste-lang.org Website], [http://hackage.haskell.org/package/haste-compiler Hackage]<br />
<br />
* Seamless, type-safe single program framework for client-server communication<br />
* Easy Javascript interoperability<br />
* Generates small, fast, minifiable code.<br />
* Lightweight concurrency, Cabal integration, FFI and GHC extensions supported.<br />
* Cross platform.<br />
* Works.<br />
<br />
=== [[JMacro]] ===<br />
<br />
On the Haskell wiki (see above) and on [http://hackage.haskell.org/package/jmacro hackage]<br />
<br />
* Mature, Maintained<br />
* Not Haskell but an EDSL _in_ Haskell nonetheless.<br />
* JMacro Panels provides a purely haskell combinator library that generates dynamically updating html and js with asynchronous client-server communication.<br />
* Syntax is a fusion of Haskell and JavaScript<br />
* Untyped, but with syntactic correctness (at least) enforced at compile-time.<br />
* Embeddable through quasi-quoting<br />
* Support for various forms of code-generation<br />
<br />
=== Others ===<br />
<br />
* [https://github.com/johang88/haskellinjavascript Haskell interpreter in JS] — An interpreter. Haven't tried but is apparently dead.<br />
* YHC JS backend — Beta-ish. Apparently works, but I was unable to compile YHC, so haven't tried yet. I would be interested in anyone's experience using it. There's [http://www.haskell.org/haskellwiki/Yhc/Javascript an old wiki page] about Yhc's JavaScript support, but Yhc itself is a dead project.<br />
* Emscripten — not Haskell→JS, but compiles LLVM/Clang output to JavaScript. Could possibly be used for GHC→LLVM→JS compiling, which I tried, and works, but would have to also compile the GHC runtime which is not straight-forward (to me) for it to actually run. <br />
* hjscript — Beta. EDSL, not Haskell→JS. Works. Not ''very'' annoying to program in, but is JS semantics, not Haskell. Hackage package [http://hackage.haskell.org/package/HJScript here.]<br />
* Some have also tried writing a Haskell→JS compiler to make a more direct JS-aware translation of code (to not have huge code output a la GHCJS, YHC, Emscripten).<br />
<br />
<br />
== FP -> JS ==<br />
<br />
=== Ur/Web ===<br />
<br />
http://www.impredicative.com/ur/<br />
<br />
Perhaps the problem with Ur is that they are selling both a backend and a frontend together. Being a new language, the backend is lacking in libraries to be practical for many tasks. However, there is an RSS reader that is using Ur for the front-end and Haskell for the backend: https://bazqux.com/<br />
<br />
<br />
=== OCaml ===<br />
<br />
The OCaml -> JS compiler is supposed to be good, it is now used at facebook for an internal in-browser code editor.<br />
http://ocsigen.org/js_of_ocaml/<br />
<br />
=== GorillaScript ===<br />
<br />
http://ckknight.github.io/gorillascript/<br />
<br />
immutable by default, global type inference, macros, what coffeescript should have been. The syntax is similar to coffeescript<br />
<br />
=== Roy, PureScript ===<br />
<br />
[http://roy.brianmckenna.org/ Roy]: meld JavaScript semantics with functional languages. Experimental, but has many bread-and-butter Haskell features.<br />
Roy is written in JS. PureScript is written in Haskell.<br />
<br />
=== Idris ===<br />
<br />
Idris is a compiled language with dependent types, implemented in Haskell, with backends for both LLVM and JavaScript. Experimental.<br />
<br />
* Full dependent types with dependent pattern matching where clauses, with rule, simple case expressions, pattern matching let and lambda bindings<br />
* Dependent records with projection and update<br />
* Type classes<br />
* Monad comprehensions<br />
* Syntactic conveniences for lists, tuples, dependent pairs do notation and idiom brackets<br />
* Indentation significant syntax<br />
* Extensible syntax<br />
* Tactic based theorem proving (influenced by Coq)<br />
* Cumulative universes<br />
* Totality checking<br />
* Simple foreign function interface (to C)<br />
* Hugs style interactive environment<br />
<br />
Links:<br />
* [http://idris-lang.org/ Website idris-lang.org] <br />
* [[Dependent_type|Dependent Type in haskell wiki]]<br />
* [http://en.wikipedia.org/wiki/Dependent_type WP (en) Dependent type] (with Idris listed under language comparison)<br />
<br />
<br />
== Links ==<br />
<br />
* [https://github.com/yesodweb/yesod/wiki/Javascript-Options Yesod - Javascript Options]<br />
* [http://chrisdone.com/tags/javascript Chris Done Blog] - Tag: Javascript<br />
<br />
== Footnotes ==<br />
<br />
# Its support for closures is commonly noted as being one of JavaScript’s redeeming features.<br />
# Early binding allows for static verification of the existence of method-signature pairs (e.g. v-tables). Late binding does not give the compiler (or an IDE) enough information for existence verification, it has to be looked up at run-time.<br />
# There are several hinting libraries, which developers insist are indispensable tools when developing JavaScript seriously, such as JavaScript lint, JSLint, and JSure.<br />
# “Any non-trivial analysis is very difficult due to Javascript’s dynamic nature.” — Berke Durak, Ph.D., author of jsure.<br />
# Google Inc. thought it necessary to develop a compiler, Google Closure, which does type-checking and limited inference.<br />
<br />
<br />
[[Category:Web|*]]</div>
Steshaw
https://wiki.haskell.org/index.php?title=Research_papers/Generics&diff=46135
Research papers/Generics
2012-06-21T02:56:07Z
<p>Steshaw: /* Overview */ Update url for Comparing Approaches to Generic Programming in Haskell</p>
<hr />
<div>__TOC__<br />
<br />
== Overview ==<br />
<br />
;[http://www.staff.science.uu.nl/~jeuri101/homepage/Publications/ComparingGpFinal.pdf Comparing Approaches to Generic Programming in Haskell]<br />
:Ralf Hinze, Johan Jeuring, and Andres Löh. To appear in Roland Backhouse, Jeremy Gibbons, Ralf Hinze, and Johan Jeuring, editors, Lecture notes of the Spring School on Datatype-Generic Programming 2006, © Springer-Verlag.<br />
<br />
;[http://www.cs.uu.nl/research/techreps/repo/CS-2008/2008-010.pdf Comparing Libraries for Generic Programming in Haskell]<br />
:Alexey Rodriguez Yakushev, Johan Jeuring, Patrik Jansson, Alex Gerdes, Oleg Kiselyov, Bruno C. d. S. Oliviera. In Andy Gill, editor, Proceedings of the ACM SIGPLAN Haskell Symposium 2008, pages 111-122, and available as an extended version: Technical report Utrecht University UU-CS-2008-010, 2008.<br />
<br />
;[http://www.cse.chalmers.se/~patrikj/papers/Concepts/ConceptsJFP_Bernardy_et_al_20100831.pdf Generic programming with C++ concepts and Haskell type classes - a comparison]<br />
:Jean-Philippe Bernardy, Patrik Jansson, Marcin Zalewski, and Sibylle Schupp. JFP, 2010. In press. An earlier and shorter version was published in Proc. ACM SIGPLAN Workshop on Generic Programming (WGP), pages 37-48. ACM, 2008 as [A comparison of C++ concepts and Haskell type classes -> http://doi.acm.org/10.1145/1411318.1411324]<br />
<br />
;[ftp://ftp.kestrel.edu/pub/papers/meertens/AFP-Portugal.ps.gz Generic Programming -- An Introduction]<br />
:Roland Backhouse, Patrik Jansson, Johan Jeuring and Lambert Meertens. Advanced Functional Programming (S. Doaitse Swierstra, editor), LNCS 1608, pp. 28-115, 1999.<br />
<br />
;[http://www.cse.chalmers.se/~patrikj/poly/polyp/polylib/ PolyLib - a polytypic function library]<br />
:Patrik Jansson and Johan Jeuring. Workshop on Generic Programming, Marstrand, June 1998.<br />
<br />
;[http://www.cse.chalmers.se/~patrikj/papers/Polytypic_Programming_AFP_1996_Jeuring_Jansson.pdf Polytypic programming]<br />
:J. Jeuring and P. Jansson. In J. Launchbury et al., editors, Advanced Functional Programming '96, volume 1129 of LNCS, pages 68-114. Springer-Verlag, 1996.<br />
<br />
==Scrap your boilerplate!==<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/hmap/index.htm Scrap your boilerplate: a practical approach to generic programming]<br />
:Ralf Laemmel and Simon Peyton Jones, Proc ACM SIGPLAN Workshop on Types in Language Design and Implementation (TLDI 2003), New Orleans, pp26-37, Jan 2003.<br />
<br />
;[http://www.cwi.nl/~ralf/syb2/ Scrap more boilerplate: reflection, zips, and generalised casts]<br />
:Ralf Laemmel and Simon Peyton Jones. appeared in Proceedings of ICFP 2004, ACM Press<br />
<br />
;[http://www.cwi.nl/~ralf/syb3/ Scrap your boilerplate with class: extensible generic functions]<br />
:Ralf Laemmel and Simon Peyton Jones. appeared in Proceedings of ICFP 2005, ACM Press<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/SYB0.pdf "Scrap Your Boilerplate" Reloaded]<br />
:Ralf Hinze, Andres Löh and Bruno C. d. S. Oliveira. In Philip Wadler and Masimi Hagiya, editors, Proceedings of the Eighth International Symposium on Functional and Logic Programming (FLOPS 2006), 24-26 April 2006, Fuji Susono, Japan.<br />
<br />
;[http://web.engr.oregonstate.edu/~erwig/reclib/ RecLib - A Recursion and Traversal Library for Haskell (Or: Scrap Your Boilerplate Systematically)]<br />
:Deling Ren and Martin Erwig, Haskell Workshop 2006<br />
<br />
;[http://www-users.cs.york.ac.uk/~ndm/uniplate/ Uniplate - Uniform Boilerplate and List Processing]<br />
:Neil Mitchell and Colin Runciman, Haskell Workshop 2007<br />
<br />
==Generic Haskell==<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications.html Generic Haskell: Applications] <br />
:Ralf Hinze and Johan Jeuring. Technical Report UU-CS-2003-16, Department of Computer Science, Utrecht University, 2003.<br />
<br />
;[http://www.cs.uu.nl/research/projects/generic-haskell/ Generic Haskell: a language for generic programming] <br />
:Johan Jeuring et al<br />
<br />
;[http://www.springerlink.com/index/F1WPGU2J9V59G4GR.pdf Generic Haskell: Practice and theory]<br />
:R Hinze, J Jeuring - lecture notes of the Summer School on Generic Programming, 2002 - Springer<br />
<br />
;[http://www.cs.uu.nl/people/stefan/pubs/holdermans06generic.html Generic views on data types]<br />
:Stefan Holdermans, Johan Jeuring, Andres Löh, and Alexey Rodriquez. In Tarmo Uustalu, editor, Mathemetics of Program Construction, 8th International Conference, MPC 2006, Kuressaare, Estonia, July 3&mdash;5, 2006, Proceedings, volume 4014 of Lecture Notes in Computer Science, pages 209&mdash;234. Springer-Verlag, 2006.<br />
<br />
;[http://homepages.cwi.nl/~atanasso/papers/atanassow04inferring.pdf Inferring type isomorphisms generically]<br />
:Frank Atanassow and Johan Jeuring. In Proc. Mathematics of Program Construction (MPC) 2004.<br />
<br />
===Applications of Generic Haskell===<br />
<br />
;[http://homepages.cwi.nl/~atanasso/papers/atanassow03scripting.pdf Scripting XML with Generic Haskell]<br />
:Frank Atanassow, Dave Clarke and Johan Jeuring. In Proc. 7th Brazilian Symposium on Programming Languages (SBLP) 2003.<br />
<br />
;[http://homepages.cwi.nl/~atanasso/papers/atanassow04uuxml.pdf UUXML: A Type-Preserving XML SchemaHaskell Data Binding]<br />
:Frank Atanassow, Dave Clarke and Johan Jeuring. In Proc. Practical Aspects of Declarative Languages (PADL) 2004.<br />
<br />
==Testing==<br />
<br />
;[http://www.springerlink.com/content/d721893h62144724/ Testing properties of generic functions]<br />
:Patrik Jansson, Johan Jeuring, and students of the Utrecht University Generic Programming class. In Zoltan Horvath, editor, Proceedings of IFL 2006, volume 4449 of LNCS, pages 217-234. Springer-Verlag, 2007.<br />
<br />
;[http://www.cse.chalmers.se/~bernardy/PolyTest.pdf Testing polymorphic properties]<br />
:Jean-Philippe Bernardy, Patrik Jansson, and Koen Claessen. In Proceedings of ESOP 2010, volume 6012 of LNCS. Springer, 2010.<br />
<br />
==DSL / applications / C++==<br />
<br />
;[http://www.springerlink.com/index/v10642g0j71m345p.pdf Generic libraries in C++ with concepts from high-level domain descriptions in Haskell: A DSL for computational vulnerability assessment.]<br />
:Daniel Lincke, Patrik Jansson, Marcin Zalewski, and Cezar Ionescu. In IFIP Working Conf. on Domain Specific Languages, volume 5658/2009 of LNCS, pages 236{261, 2009.<br />
<br />
;[http://dx.doi.org/10.1016/S0167-6423(01)00020-X Polytypic data conversion programs]<br />
:Patrik Jansson and Johan Jeuring. Science of Computer Programming, 43(1):35-75, 2002. An earlier version was published as "Polytypic compact printing and parsing" in Doaitse Swierstra, editor, ESOP'99: European Symposium on Programming, volume 1576 of LNCS, pages 273-287. Springer-Verlag, 1999.<br />
<br />
;[http://www.cse.chalmers.se/~patrikj/poly/terms/polytermsandrewriting.ps.gz A framework for polytypic programming on terms, with an application to rewriting]<br />
:Patrik Jansson and Johan Jeuring. In Workshop on Generic Programming. Utrecht University, 2000. UU-CS-2000-19.<br />
<br />
;[http://portal.acm.org/citation.cfm?id=969590 Functional pearl: Polytypic unification]<br />
:Patrik Jansson and Johan Jeuring. J. Funct. Program., 8(5):527-536, 1998.<br />
<br />
==Theory, cata, etc.==<br />
<br />
;[http://www.cse.chalmers.se/%7Ebernardy/ParDep/pardep.pdf Parametricity and dependent types]<br />
:Jean-Philippe Bernardy, Patrik Jansson, and Ross Paterson. In Proceedings of ICFP 2010, pages 345-356, Baltimore, Maryland, 2010. ACM.<br />
<br />
;[http://www.iis.sinica.edu.tw/~scm/pub/aopa.pdf Algebra of programming in Agda: dependent types for relational program derivation]<br />
:Shin-Cheng Mu, Hsiang-Shang Ko, and Patrik Jansson. J. Funct. Program., 19:545-579, 2009. Earlier version published as "Algebra of programming using dependent types" in Mathematics of Program Construction, volume 5133/2008 of LNCS, pages 268-283. Springer-Verlag, 2008.<br />
<br />
:[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.58.2150&rep=rep1&type=pdf Universes for generic programs and proofs in dependent type theory]<br />
;Marcin Benke, Peter Dybjer, and Patrik Jansson. Nordic Journal of Computing, 10(4):265{289, 2003.<br />
<br />
;[http://www.cse.chalmers.se/~patrikj/papers/polypPOPL97.pdf PolyP - a polytypic programming language extension]<br />
:P. Jansson and J. Jeuring. In Proc. POPL'97: Principles of Programming Languages, pages 470-482. ACM Press, 1997.<br />
<br />
==Other==<br />
<br />
;[http://www.cse.chalmers.se/~ulfn/papers/genericth.pdf Prototyping generic programming in Template Haskell]<br />
:Ulf Norell and Patrik Jansson. In Dexter Kozen, editor, Mathematics of Program Construction, volume 3125 of LNCS, pages 314-333. Springer-Verlag, 2004.<br />
<br />
;[http://www.cse.chalmers.se/~ulfn/papers/polyhaskell.pdf Polytypic programming in Haskell]<br />
:Ulf Norell and Patrik Jansson. In Phil Trinder, Greg Michaelson, and Ricardo Peña, editors, Implementation of Functional Languages 2003, 15th International Workshop, volume 3145 of LNCS, pages 168-184. Springer-Verlag, 2004.<br />
<br />
;[http://publications.lib.chalmers.se/records/fulltext/804.pdf Functional Polytypic Programming]<br />
:Patrik Jansson. PhD thesis, Computing Science, Chalmers University of Technology and Göteborg University, Sweden, May 2000.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/ICFP04.pdf Generics for the masses]<br />
:Ralf Hinze. In Kathleen Fisher, editor, Proceedings of the 2004 International Conference on Functional Programming, Snowbird, Utah, September 19-22, 2004.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/HW2002.ps.gz A Lightweight Implementation of Generics and Dynamics]<br />
:James Cheney and Ralf Hinze. In Manuel Chakravarty, editor, Proceedings of the ACM SIGPLAN 2002 Haskell Workshop, Pittsburgh, PA, USA, October 3, 2002, pp 90-104.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/Tidata.ps.gz Type-indexed data types]<br />
:Ralf Hinze, Johan Jeuring, Andres Löh. In Eerke Boiten, Bernhard Möller, editors, Proceedings of the Sixth International Conference on Mathematics of Program Construction (MPC 2002), Dagstuhl, Germany, July 8-10, 2002. Lecture Notes in Computer Science 2386, pp. 148-174.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/WGP00b.ps.gz Memo functions, polytypically!]<br />
:Ralf Hinze. In Johan Jeuring, editor, Proceedings of the Second Workshop on Generic Programming, WGP 2000, Ponte de Lima, Portugal, 6th July 2000.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/WGP00a.ps.gz Efficient Generalized Folds]<br />
:Ralf Hinze. In Johan Jeuring, editor, Proceedings of the Second Workshop on Generic Programming, WGP 2000, Ponte de Lima, Portugal, 6th July 2000.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/MPC00.ps.gz Polytypic values possess polykinded types]<br />
:Ralf Hinze. In Roland Backhouse, J.N. Oliveira, editors, Proceedings of the Fifth International Conference on Mathematics of Program Construction (MPC 2000), Ponte de Lima, Portugal, July 3-5, 2000.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/POPL00.ps.gz A New Approach to Generic Functional Programming] <br />
:Ralf Hinze. In Proceedings of the 27th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Boston, Massachusetts, January 19-21, 2000.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/FLOPS99.ps.gz Polytypic Programming with Ease]<br />
:Ralf Hinze. In 4th Fuji International Symposium on Functional and Logic Programming (FLOPS'99), Tsukuba, Japan, November 1999, pp. 21-36. Lecture Notes in Computer Science 1722.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/HW99.ps.gz A Generic Programming Extension for Haskell]<br />
:Ralf Hinze. In Erik Meijer, editor, Proceedings of the Third Haskell Workshop, Paris, France, September 1999. The proceedings appear as a technical report of Universiteit Utrecht, UU-CS-1999-28.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/CLAPF99.ps.gz Polytypic Functions Over Nested Datatypes]<br />
:Ralf Hinze. In Rafael Dueire Lins, editor, 3rd Latin-American Conference on Functional Programming (CLaPF'99), March 1999.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/habilitation.pdf Generic Programs and Proofs]<br />
:Ralf Hinze. Habilitationsschrift, Universitt Bonn, October 2000.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications.html Type-indexed data types]<br />
:Ralf Hinze, Johan Jeuring, and Andres Löh. Technical Report UU-CS-2002-11, Department of Computer Science, Utrecht University, 2002.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications.html Combining generics and dynamics] <br />
:Peter Achten and Ralf Hinze. Technical Report NIII-R0206, Nijmegen Institute for Computing and Information Sciences, University of Nijmegen, July 2002.<br />
<br />
;[http://homepages.cwi.nl/~ralf/wrs04/ Programmable rewriting strategies in Haskell]<br />
:Ralf Lämmel, Invited paper, Proceedings of WRS 2004 13 pages To appear in ENTCS, 2004<br />
<br />
;[http://homepages.cwi.nl/~ralf/padl03/ A Strafunski Application Letter]<br />
:Ralf Lämmel and Joost Visser, Proc. of Practical Aspects of Declarative Programming (PADL'03), LNCS 2562, 2003, 357--375.<br />
<br />
;[http://homepages.cwi.nl/~ralf/wgp00/ Dealing with Large Bananas]<br />
:Ralf Lämmel and Joost Visser and Jan Kort, 46--59, WGP00 Proceedings of WGP'2000, Technical Report, Universiteit Utrecht<br />
<br />
;[http://www.cwi.nl/~ralf/just-two/ Strategic polymorphism requires just two combinators!]<br />
:Ralf Lämmel and Joost Visser, arXiv, cs.PL/0212048, 2002<br />
<br />
;[http://homepages.cwi.nl/~ralf/sfp00/ Type-safe Functional Strategies]<br />
:Ralf Lämmel and Joost Visser, draft proceedings of SFP'00, St Andrews, 2000.<br />
<br />
;[http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/typecase.pdf TypeCase: A Design Pattern for Type-Indexed Functions] <br />
:Bruno C. d. S. Oliveira and Jeremy Gibbons (2005). Haskell Workshop, September 2005.<br />
<br />
;[http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/hodgp.pdf Design Patterns as Higher-Order Datatype-Generic Programs]<br />
:Jeremy Gibbons (2006). Submitted for publication.<br />
<br />
;[ftp://ftp.kestrel.edu/pub/papers/meertens/Fpull.ps Functor Pulling]<br />
:Lambert Meertens. Proceedings of the International Workshop on Generic Programming (WGP'98), Marstrand, Sweden, June 1998.<br />
<br />
;[http://www.kestrel.edu/home/people/meertens/diverse/calc.pdf Calculemus Igitur!]<br />
:Lambert Meertens, Presented at The Fun of Programming, a Symposium in honour of Richard Bird's 60th birthday<br />
<br />
;[ftp://ftp.kestrel.edu/pub/papers/meertens/pp.ps Calculate Polytypically!]<br />
:Lambert Meertens, Programming Languages: Implementations Logics, and Programs, Proceedings PLILP '96 (Herbert Kuchen and S. Doaitse Swierstra, editors), LNCS 1140, pp. 1--16, 1996.<br />
<br />
;[http://www.kestrel.edu/home/people/meertens/diverse/ct4pc.pdf Category Theory for Program Construction] <br />
:Lambert Meertens, Lecture Notes for ESSLLI '95, Barcelona, Catalunya.<br />
<br />
;[http://www.seas.upenn.edu/~sweirich/RepLib/haskell08-weirich.pdf RepLib: A Library for Derivable Type Classes] <br />
:Stephanie Weirich. Haskell Workshop, Portland, OR, USA, September 2006.<br />
<br />
;[http://journals.cambridge.org/action/displayFulltext?type=1&fid=409644&jid=JFP&volumeId=-1&issueId=-1&aid=409643 Type-safe Runtime Polytypic Programming] <br />
:Stephanie Weirich. To appear in Journal of Functional Programming, 2006.<br />
<br />
;[http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/parametric.pdf Parametric datatype-genericity]<br />
:Jeremy Gibbons and Ross Paterson. Submitted for publication.<br />
<br />
<br />
[[Category:Research]]</div>
Steshaw
https://wiki.haskell.org/index.php?title=Orphan_instance&diff=45630
Orphan instance
2012-05-11T03:08:54Z
<p>Steshaw: </p>
<hr />
<div>An orphan instance is a type class instance for class C and type T which is neither defined in the module where C is defined nor in the module where T is defined.<br />
<br />
Type class instances are special in that they don't have a name and cannot be imported explicitly. This also means that they cannot be ''excluded'' explicitly. All instances defined in a module A are imported automatically when importing A, or importing any module that imports A, directly or indirectly.<br />
<br />
Say you want to define an alternative instance to an existing instance. This is a bad thing, since if two instances for the same class/type pair are in scope, then you cannot describe in Haskell 98 which instance to use. If you want to use multiple instances for the same class/type, you have to ensure that they are never imported together in a module somewhen. It is almost impossible to assert that, or put differently, it would reduce the composability of libraries considerably.<br />
<br />
The <hask>Monad</hask> instance of <hask>Either</hask> is a good example.<br />
It is not defined where <hask>Either</hask> is defined, thus all of its <hask>Monad</hask> instances must be orphan.<br />
Instead it is defined both in <hask>Control.Monad.Error</hask> of the [[Monad Transformer Library]]<br />
and in <hask>Control.Monad.Trans.Error</hask> of its lightweight cousin the 'transformers' package.<br />
Since some packages use MTL and others 'transformers' it becomes difficult to use that instance at all,<br />
although both instances are equivalent!<br />
Practical advice:<br />
The [[Exception|explicit-exception]] package with its <hask>Exceptional</hask> might be a better choice to use since it avoids the current problem with orphan Monad instances of <hask>Either</hask>.<br />
<br />
Actually, non-orphan instances can avoid definition of [[multiple instances]]. For defining an instance you have to import the class and the type and then you will automatically have the according non-orphan instances imported, too. If you want to define a new instance then the compiler will reject it immediately.<br />
<br />
<br />
A last advice:<br />
If you encounter a missing instance for a class or a type of a package,<br />
resist to define your own orphan instance, because it will likely collide with such instances of other packages,<br />
or it will collide with new instances added in later versions of that package.<br />
Instead ask the package author to add your instance.<br />
Sometimes it turns out that the instance was not included for the good reason<br />
that there is more than one reasonable instance definition.<br />
If your instance cannot be included, follow the advices in the article about [[multiple instances]].<br />
<br />
<br />
== See also ==<br />
<br />
* [[Multiple instances]]<br />
* Libraries mailing list on [http://www.haskell.org/pipermail/libraries/2008-August/010399.html Orphan instances can be good]<br />
* [http://modula3.elegosoft.com/pm3/pkg/modula3/src/discussion/partialRev.html Partial Revelation feature] of Modula-3 which causes similar problems like Haskell's type class instances<br />
<br />
[[Category:FAQ]]<br />
[[Category:Style]]</div>
Steshaw
https://wiki.haskell.org/index.php?title=Orphan_instance&diff=45629
Orphan instance
2012-05-11T03:07:44Z
<p>Steshaw: </p>
<hr />
<div>An orphan instance is a type class instance for class C and type T which is neither defined in the module where C is defined nor in the module where T is defined.<br />
<br />
Type class instances are special in that they don't have a name and cannot be imported explicitly. This also means that they cannot be ''excluded'' explicitly. All instances defined in a module A are imported automatically when importing A, or importing any module that imports A, directly or indirectly.<br />
<br />
Say you want to define an alternative instance to an existing instance. This is a bad thing, since if two instances for the same class/type pair are in scope, then you cannot describe in Haskell 98 which instance to use. If you want to use multiple instances for the same class/type, you have to ensure that they are never imported together in a module somewhen. It is almost impossible to assert that, or put differently, it would reduce the composability of libraries considerably.<br />
<br />
The <hask>Monad</hask> instance of <hask>Either</hask> is a good example.<br />
It is not defined where <hask>Either</hask> is defined, thus all of its <hask>Monad</hask> instances must be orphan.<br />
Instead it is defined both in <hask>Control.Monad.Error</hask> of the [[Monad Transformer Library]]<br />
and in <hask>Control.Monad.Trans.Error</hask> of its lightweight cousin the 'transformers' package.<br />
Since some packages use MTL and others 'transformers' it becomes difficult to use that instance at all,<br />
although both instances are equivalent!<br />
Practical advice:<br />
The [[Exception|explicit-exception]] package with its <hask>Exceptional</hask> might be a better choice to use since it avoids the current problem with orphan Monad instances of <hask>Either</hask>.<br />
<br />
Actually, non-orphan instances can avoid definition of [[multiple instances]]. For defining an instance you have to import the class and the type and then you will automatically have the according non-orphan instances imported, too. If you want to define a new instance then the compiler will reject it immediately.<br />
<br />
<br />
A last advice:<br />
If you encounter a missing instance for a class or a type of a package,<br />
resist to define your own orphan instance, because it will likely collide with such instances of other packages,<br />
or it will collide with new instances added in later versions of that package.<br />
Instead ask the package author to add your instance.<br />
Sometimes it turns out that the instance was not included for a good reason,<br />
that there is more than one reasonable instance definition.<br />
If your instance cannot be included, follow the advices in the article about [[multiple instances]].<br />
<br />
<br />
== See also ==<br />
<br />
* [[Multiple instances]]<br />
* Libraries mailing list on [http://www.haskell.org/pipermail/libraries/2008-August/010399.html Orphan instances can be good]<br />
* [http://modula3.elegosoft.com/pm3/pkg/modula3/src/discussion/partialRev.html Partial Revelation feature] of Modula-3 which causes similar problems like Haskell's type class instances<br />
<br />
[[Category:FAQ]]<br />
[[Category:Style]]</div>
Steshaw
https://wiki.haskell.org/index.php?title=List_function_suggestions&diff=44287
List function suggestions
2012-01-30T14:16:01Z
<p>Steshaw: /* groupOn and sortOn */ fix type signatures for groupOn + groupOn'</p>
<hr />
<div>This page lists proposed extensions to the Haskell list functions, whether in the [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html Prelude] or [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html Data.List].<br />
Please discuss the proposals on the Talk Page or the libraries list, and use this page to record the results of discussions.<br />
However, since the advent of [[Hackage]]DB and [[Cabal-Install]] it is preferred to provide such functionality in specialised packages, rather than extending the already large base library.<br />
<br />
== Splitting on a separator, etc ==<br />
<br />
We need these useful functions in Data.List; I'll call them 'split' (and variants) and 'replace'. These are easily implemented but everyone always reinvents them. Various versions have been proposed, but there was no consensus on which was best, e.g.<br />
<br />
* [http://www.haskell.org/pipermail/haskell-cafe/2006-July/thread.html#16559 haskell-cafe thread July 2006]<br />
* [http://www.haskell.org/pipermail/libraries/2004-July/thread.html#2342 libraries thread July 2004]<br />
<br />
Note: a lot of good points (diverging opinions!) are covered in the mailing lists, but if we include all these various cases, split* will have 9 variants! The goal is to reach some kind of reasonable consensus, specifically on naming and semantics. Even if we need pairs of functions to satisfy various usage and algebraic needs. Failing to accommodate every possible use of these functions should not be a sufficient reason to abandon the whole project.<br />
<br />
The goal is clarity/uniformity (everyone uses them widely and recognizes them) and portability (I don't have to keep reimplementing these or copying that one file UsefulMissingFunctions.hs).<br />
<br />
Note: I (Jared Updike) am working with the belief that efficiency should not be a valid argument to bar these otherwise universally useful functions from the libraries; regexes are overkill for 'split' and 'replace' for common simple situations. Let's assume people will know (or learn) when they need heavier machinery (regexes, ByteString) and will use it when efficiency is important. We can try to facilitate this by reusing any names from ByteString, etc.<br />
<br />
=== split (working name) ===<br />
<br />
First of all: Check out whether the [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/split split] package provides, what you need.<br />
<br />
We need a few of these:<br />
<br />
<haskell><br />
split :: Eq a => a -> [a] -> [[a]]<br />
splitWith :: (a -> Bool) -> [a] -> [[a]]<br />
tokens :: (a -> Bool) -> [a] -> [[a]]<br />
</haskell><br />
<br />
That preserve:<br />
<br />
<haskell><br />
join sep . split sep = id<br />
</haskell><br />
<br />
See below for 'join'<br />
<br />
And some that use above split but filter to remove empty elements (but do not preserve above property). Easy enough:<br />
<br />
<haskell><br />
split' :: Eq a => a -> [a] -> [[a]]<br />
splitWith' :: (a -> Bool) -> [a] -> [[a]]<br />
tokens' :: (a -> Bool) -> [a] -> [[a]]<br />
</haskell><br />
<br />
i.e.<br />
<br />
<haskell><br />
split' sep = filter (not . null) . split sep<br />
</haskell><br />
<br />
Usage would be:<br />
<br />
<haskell><br />
tokensws = tokens' (`elem` " \f\v\t\n\r\b")<br />
<br />
tokensws "Hello there\n \n Haskellers! " ==<br />
["Hello", "there", "Haskellers!"]<br />
</haskell><br />
<br />
'''TODO: add version like python with multi-element separator'''<br />
<br />
'''TODO: give code, copy-paste from threads mentioned above'''<br />
<br />
'''TODO: list names and reasons for/against'''<br />
<br />
=== replace (working name) ===<br />
<br />
<haskell><br />
replace :: [a] -> [a] -> [a] -> [a]<br />
</haskell><br />
<br />
like Python replace:<br />
<br />
<haskell><br />
replace "the" "a" "the quick brown fox jumped over the lazy black dog"<br />
===><br />
"a quick brown fox jumped over a lazy black dog"<br />
</haskell><br />
<br />
'''TODO: give code, copy-paste from threads mentioned above'''<br />
<br />
'''TODO: list names and reasons for/against'''<br />
<br />
Implemented for instance in [http://hackage.haskell.org/packages/archive/utility-ht/0.0.1/doc/html/Data-List-HT.html#v%3Areplace utility-ht].<br />
<br />
=== join (working name) ===<br />
<br />
<haskell><br />
join :: [a] -> [[a]] -> [a]<br />
</haskell><br />
<br />
<haskell><br />
join sep = concat . intersperse sep<br />
</haskell><br />
<br />
Note: this function has been implemented as 'intercalate' in Data.List.<br />
<br />
'''TODO: copy-paste things from threads mentioned above'''<br />
<br />
'''TODO: list names and reasons for/against'''<br />
<br />
== Sorted lists ==<br />
<br />
The following are versions of standard prelude functions, but intended for sorted lists. The advantage is that they frequently reduce execution time by an O(n). The disadvantage is that the elements have to be members of Ord, and the lists have to be already sorted.<br />
<br />
<haskell><br />
-- Eliminates duplicate entries from the list, where duplication is defined<br />
-- by the 'eq' function. The last value is kept.<br />
sortedNubBy :: (a -> a -> Bool) -> [a] -> [a]<br />
sortedNubBy eq (x1 : xs@(x2 : _)) =<br />
if eq x1 x2 then sortedNubBy eq xs else x1 : sortedNubBy eq xs<br />
sortedNubBy _ xs = xs<br />
<br />
sortedNub :: (Eq a) => [a] -> [a]<br />
sortedNub = sortedNubBy (==)<br />
<br />
-- Merge two sorted lists into a new sorted list. Where elements are equal<br />
-- the element from the first list is taken first.<br />
mergeBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]<br />
mergeBy cmp xs@(x1:xs1) ys@(y1:ys1) =<br />
if cmp x1 y1 == GT<br />
then y1 : mergeBy cmp xs ys1<br />
else x1 : mergeBy cmp xs1 ys<br />
mergeBy _ [] ys = ys<br />
mergeBy _ xs [] = xs<br />
<br />
merge :: (Ord a) => [a] -> [a] -> [a]<br />
merge = mergeBy compare<br />
</haskell><br />
<br />
<hask>mergeBy</hask> is implemented in [http://hackage.haskell.org/packages/archive/utility-ht/0.0.1/doc/html/Data-List-HT.html#v%3AmergeBy utility-ht].<br />
<br />
== Generalize groupBy and friends ==<br />
<br />
In the Haskell 98 List library, <hask>groupBy</hask> assumes that its argument function defines an equivalence, and the reference definition returns sublists where each element is equivalent to the first. The following definition, comparing adjacent elements, does the same thing on equivalence relations:<br />
<haskell><br />
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]<br />
groupBy rel [] = []<br />
groupBy rel (x:xs) = (x:ys) : groupBy rel zs<br />
where (ys,zs) = groupByAux x xs<br />
groupByAux x0 (x:xs) | rel x0 x = (x:ys, zs)<br />
where (ys,zs) = groupByAux x xs<br />
groupByAux y xs = ([], xs)<br />
</haskell><br />
However it is also useful on other relations, e.g.<br />
* Picking out maximal ascending sublists (runs):<br />
<haskell><br />
> groupBy (<=) [7,3,5,9,6,8,3,5,4]<br />
[[7],[3,5,9],[6,8],[3,5],[4]]<br />
</haskell><br />
* Picking out contiguous sublists from an ascending sequence:<br />
<haskell><br />
> groupBy (\a b -> a+1 == b) [1,2,3,4,6]<br />
[[1,2,3,4],[6]]<br />
</haskell><br />
* Splitting a line at the start of each word:<br />
<haskell><br />
> groupBy (\ c1 c2 -> isLetter c1 || not (isLetter c2)) "This is a line"<br />
["This ","is ","a ","line"]<br />
</haskell><br />
Since this more useful definition agrees with the Haskell 98 one on its specified domain, it should be a backwards-compatible replacement.<br />
<br />
The same applies to <hask>nubBy</hask>, and possibly <hask>deleteBy</hask>, <hask>deleteFirstsBy</hask> and <hask>intersectBy</hask> (which could have more general types to make this clear).<br />
<br />
See:<br />
* Libraries list on [http://www.haskell.org/pipermail/libraries/2007-August/008028.html Data.List.groupBy with non-transitive equality predicate]<br />
* Implementation in [http://hackage.haskell.org/packages/archive/utility-ht/0.0.1/doc/html/Data-List-HT.html#v%3AgroupBy utility-ht]<br />
<br />
== groupOn and sortOn ==<br />
<br />
Almost all uses of <hask>groupBy</hask> and <hask>sortBy</hask> actually use a specific compare function. This can (using a recent version of base) as<br />
<hask>sortBy (comparing fst)</hask><br />
or<br />
<hask>sortBy (compare `on` fst)</hask>.<br />
Since this use is so common, it might be worthwhile to add separate functions for this:<br />
<haskell><br />
sortOn :: Ord b => (a -> b) -> [a] -> [a]<br />
sortOn = sortBy . comparing<br />
</haskell><br />
The same goes for <hask>groupBy</hask><br />
<haskell><br />
groupOn :: Eq b => (a -> b) -> [a] -> [[a]]<br />
groupOn f = groupBy ((==) `on` f)<br />
</haskell><br />
That is,<br />
<haskell><br />
groupOn' :: Eq b => (a -> b) -> [a] -> [[a]]<br />
groupOn' f = groupBy (\x y -> f x == f y)<br />
</haskell><br />
The names could be better, the idea behind 'on' comes from the 'on' function.<br />
<br />
See [http://hackage.haskell.org/packages/archive/utility-ht/0.0.1/doc/html/Data-List-Key.html utility-ht] package.<br />
<br />
== See also ==<br />
* [[Prelude extensions]]<br />
* [[Hackage]]<br />
<br />
[[Category:Proposals]]<br />
[[Category:Standard libraries]]<br />
[[Category:Idioms]]</div>
Steshaw
https://wiki.haskell.org/index.php?title=Category_theory&diff=42754
Category theory
2011-11-05T03:41:23Z
<p>Steshaw: Fix link to paper</p>
<hr />
<div>{{Foundations infobox}}<br />
'''Category theory''' can be helpful in understanding Haskell's type system. There exists a "Haskell category", of which the objects are Haskell types, and the morphisms from types <hask>a</hask> to <hask>b</hask> are Haskell functions of type <hask>a -> b</hask>. Various other Haskell structures can be used to make it a Cartesian closed category.<br />
<br />
__TOC__<br />
<br />
The Haskell wikibooks has [http://en.wikibooks.org/wiki/Haskell/Category_theory an introduction to Category theory], written specifically with Haskell programmers in mind.<br />
<br />
==Definition of a category==<br />
<br />
<br />
A category <math>\mathcal{C}</math>consists of two collections:<br />
<br />
Ob<math>(\mathcal{C})</math>, the objects of <math>\mathcal{C}</math><br />
<br />
Ar<math>(\mathcal{C})</math>, the arrows of <math>\mathcal{C}</math><br />
(which are not the same as [[Arrow]]s defined in [[GHC]])<br />
<br />
Each arrow <math>f</math> in Ar<math>(\mathcal{C})</math> has a<br />
domain, dom <math>f</math>, and a codomain, cod <math>f</math>, each<br />
chosen from Ob<math>(\mathcal{C})</math>. The notation <math>f\colon<br />
A \to B</math> means <math>f</math> is an arrow with domain<br />
<math>A</math> and codomain <math>B</math>. Further, there is a<br />
function <math>\circ</math> called composition, such that <math>g<br />
\circ f</math> is defined only when the codomain of <math>f</math> is<br />
the domain of <math>g</math>, and in this case, <math>g \circ f</math><br />
has the domain of <math>f</math> and the codomain of <math>g</math>. <br />
<br />
In symbols, if <math>f\colon A \to B</math> and <math>g\colon B \to<br />
C</math>, then <math>g \circ f \colon A \to C</math>. <br />
<br />
Also, for each object <math>A</math>, there is an arrow<br />
<math>\mathrm{id}_A\colon A \to A</math>, (often simply denoted as<br />
<math>1</math> or <math>\mathrm{id}</math>, when there is no chance of<br />
confusion). <br />
<br />
===Axioms===<br />
The following axioms must hold for <math>\mathcal{C}</math> to be a category:<br />
<br />
#If <math>f\colon A \to B</math> then <math>f \circ \mathrm{id}_A = \mathrm{id}_B\circ f = f</math> (left and right identity) <br />
#If <math>f\colon A \to B</math> and <math>g \colon B \to C</math> and <math>h \colon C \to D</math>, then <math>h \circ (g \circ f) = (h<br />
\circ g) \circ f</math> (associativity) <br />
<br />
===Examples of categories===<br />
* Set, the category of sets and set functions.<br />
* Mon, the category of monoids and monoid morphisms.<br />
* Monoids are themselves one-object categories.<br />
* Grp, the category of groups and group morphisms.<br />
* Rng, the category of rings and ring morphisms.<br />
* Grph, the category of graphs and graph morphisms.<br />
* Top, the category of topological spaces and continuous maps.<br />
* Preord, the category of preorders and order preserving maps.<br />
* CPO, the category of complete partial orders and continuous functions.<br />
* Cat, the category of categories and functors.<br />
<br />
* [[Hask]]<br />
* the category of data types and functions on data structures <br />
* the category of functions and data flows (~ data flow diagram)<br />
* the category of stateful objects and dependencies (~ object diagram)<br />
* the category of values and value constructors<br />
* the category of states and messages (~ state diagram)<br />
<br />
===Further definitions===<br />
With examples in Haskell at:<br />
* [[Category theory/Functor]]<br />
* [[Category theory/Natural transformation]]<br />
* [[Category theory/Monads]]<br />
<br />
== Categorical programming ==<br />
<br />
Catamorphisms and related concepts, categorical approach to functional programming, categorical programming. Many materials cited here refer to category theory, so as an introduction to this discipline see the [[#See also]] section.<br />
* Erik Meijer, Maarten Fokkinga, Ross Paterson: [http://research.microsoft.com/en-us/um/people/emeijer/Papers/fpca91.pdf Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire]. See also related documents (in the CiteSeer page). Understanding the article does not require knowledge of category theory—the paper is self-contained with regard to understanding catamorphisms, anamorphisms and other related concepts.<br />
* Roland Backhouse, Patrik Jansson, Johan Jeuring and Lambert Mertens. [http://www.cse.chalmers.se/~patrikj/poly/afp98/ Generic Programming - an Introduction]: Detailed introduction to categorial sums, product, polynomial functors and folds for the purpose of generic programming. Supplements the bananas paper.<br />
* Varmo Vene and Tarmo Uustalu: [http://citeseer.ist.psu.edu/vene98functional.html Functional Programming with Apomorphisms / Corecursion]<br />
* Varmo Vene: [http://www.cs.ut.ee/~varmo/papers/thesis.pdf Categorical Programming with Inductive and Coinductive Types]. The book gives Haskell examples to illustrate the deep categorical theory topic.<br />
* Tatsuya Hagino: [http://www.tom.sfc.keio.ac.jp/~hagino/thesis.pdf A Categorical Programming Language]<br />
* [http://pll.cpsc.ucalgary.ca/charity1/www/home.html Charity], a categorical programming language implementation.<br />
* [http://okmij.org/ftp/Haskell/categorical-maxn.lhs Deeply uncurried products, as categorists might like them] article mentions a conjecture: relatedness to [[Combinatory logic]]<br />
<br />
==Haskell libraries and tools==<br />
<br />
* [http://www.eyrie.org/~zednenem/2004/hsce/ Category extras] by [http://www.eyrie.org/~zednenem/about/dave.html David Menendez]: libraries for e.g. comonads, infinite data types.<br />
<br />
==Books==<br />
<br />
*Michael Barr and Charles Wells: [http://www.cwru.edu/artsci/math/wells/pub/ttt.html Toposes, Triples and Theories]. The online, freely available book is both an introductory and a detailed description of category theory. It also contains a category-theoretical description of the concept of ''monad'' (but calling it a ''triple'' instead of ''monad'').<br />
<br />
*R. F. C. Walters: [http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=0521419972 Categories and Computer Science]. Category Theory has, in recent years, become increasingly important and popular in computer science, and many universities now introduce Category Theory as part of the curriculum for undergraduate computer science students. Here, the theory is developed in a straightforward way, and is enriched with many examples from computer science.<br />
<br />
* Arbib&Manes: Arrow, Structures and Functors - The Categorical Imperative. (c)1975 Academic Press, ISBN 0-12-059060-3. Sadly now out of print but very little prerequisite knowledge is needed. It covers monads and the Yoneda lemma.<br />
<br />
==See also==<br />
<br />
* Michael Barr and Charles Wells have a [http://www.math.upatras.gr/~cdrossos/Docs/B-W-LectureNotes.pdf paper] that presents category theory from a computer-science perspective, assuming no prior knowledge of categories.<br />
*[http://wwwhome.cs.utwente.nl/~fokkinga/mmf92b.html A Gentle Introduction to Category Theory - the calculational approach] written by [http://wwwhome.cs.utwente.nl/~fokkinga/index.html Maarten M Fokkinga].<br />
* Wikipedia has a good [http://en.wikipedia.org/wiki/List_of_category_theory_topics collection of category-theory articles], although, as is typical of Wikipedia articles, they are rather dense.<br />
<br />
[[Category:Theoretical foundations]]<br />
[[Category:Mathematics]]</div>
Steshaw
https://wiki.haskell.org/index.php?title=User:Steshaw&diff=42753
User:Steshaw
2011-11-05T03:33:44Z
<p>Steshaw: </p>
<hr />
<div>Steven Shaw is dedicated to mastering the art of Haskell programming :)<br />
<br />
More at [http://steshaw.org/ steshaw.org].</div>
Steshaw
https://wiki.haskell.org/index.php?title=User:Steshaw&diff=37982
User:Steshaw
2010-12-22T10:52:08Z
<p>Steshaw: </p>
<hr />
<div>Steven Shaw is dedicated to mastering the art of Haskell programming :)<br />
<br />
More at [http://steshaw.org/ steshaw.org]. Works for [http://codefu.com.au Code Fu].</div>
Steshaw
https://wiki.haskell.org/index.php?title=OzHaskell&diff=37357
OzHaskell
2010-10-30T02:18:49Z
<p>Steshaw: </p>
<hr />
<div>'''There is AngloHaskell and now AmeroHaskell. Doesn't that call for OzHaskell?'''<br />
<br />
Who would be interested to have a Haskell event in Australia, possibly in Sydney? This is just a wild idea without any concrete date or format yet. Jot down any suggestions on this page.<br />
<br />
Interested Haskellers:<br />
<br />
* [[:User:Chak|Manuel Chakravarty]] (Sydney)<br />
* [[:User:TonyMorris|Tony Morris]] (Brisbane)<br />
* [[:User:Brecknell|Matthew Brecknell]] (Brisbane, will travel, prefer late Jan)<br />
* [[:User:Mark_Wassell|Mark Wassell]] - Prefer Jan/Feb option.<br />
* [[:User:Rl|Roman Leshchinskiy]]<br />
* [[:User:cbrad|Brad Clow]] (Brisbane)<br />
* [[:User:nornagon|Jeremy Apthorp]]<br />
* [[:User:AndrewA|Andrew Appleyard]] (Sydney)<br />
* [[:User:bjpop|Bernie Pope]] (Melbourne)<br />
* [[:User:benl23|Ben Lippmeier]]<br />
* [[:User:RohanDrape|Rohan Drape]] (Melbourne)<br />
* [[:User:ivanm|Ivan Miljenovic]] (Canberra)<br />
* [[:User:EricWilligers|Eric Willigers]]<br />
* [[:User:TonySloane|Tony Sloane]] (Sydney)<br />
* [[:User:Bens|Ben Sinclair]] (Sydney)<br />
* [[:User:andrep|Andre Pang]]<br />
* [[:User:AndrewBromage|Andrew Bromage]] (Melbourne)<br />
* [[:User:Droberts|Dale Roberts]] (Sydney)<br />
* [[:User:GeoffWilson|Geoff Wilson]] (Melbourne)<br />
* [[:User:Saulzar|Oliver Batchelor]] (Brisbane)<br />
* [[:User:Nick|Nick Seow]] (Sydney)<br />
* [[:User:sseefried|Sean Seefried]] (Sydney)<br />
* [[:User:green_tea|Alexis Hazell]] (Melbourne)<br />
* [[:User:PhilipDerrin|Philip Derrin]] (Sydney)<br />
* [[:User:Jeeva|Jeeva]] (Sydney)<br />
* [[:User:michaelneale|Michael Neale]] (Brisbane)<br />
* [[:User:rus|Ruslan Abdulkhalikov]] (Sydney)<br />
* [[:User:doverton|David Overton]] (London, soon to be Melbourne)<br />
* [[:User:mleeming|Michael Leeming]] (Sydney)<br />
* [[:User:horsfall|Ben Horsfall]] (Melbourne)<br />
* [[:User:trh|Toby Hutton]] (Melbourne)<br />
* [[:User:OJ|OJ Reeves]] (Brisbane)<br />
* [[:User:mwotton|Mark Wotton]] (Sydney)<br />
* [[:User:isaacsu | Isaac Su]] (Melbourne)<br />
* [[:User:steshaw|Steven Shaw]] (Brisbane)<br />
<br />
(Add your name!)<br />
<br />
== Possible dates ==<br />
<br />
== Format ==<br />
<br />
How about the following?<br />
<br />
* One day meeting with informal talks and demos (preferably on a Friday)<br />
* There could be a second, even less formal day, for those who want to hang out some more and maybe some hacking<br />
* Run it at the University of New South Wales, Sydney<br />
<br />
(Add your thoughts to the above.)<br />
<br />
== Talks and demos ==<br />
<br />
Do you have anything you'd like to talk about or a system you'd like to demo? '''This is just a tentative list - you commit to nothing.'''<br />
<br />
=== Talk proposals ===<br />
<br />
=== Demo proposals ===<br />
<br />
[[Category:Events]]</div>
Steshaw
https://wiki.haskell.org/index.php?title=User:Steshaw&diff=37356
User:Steshaw
2010-10-30T02:16:30Z
<p>Steshaw: </p>
<hr />
<div>Steven Shaw is dedicated to mastering the art of Haskell programming :)<br />
<br />
More at [http://steshaw.org/ steshaw.org]. Works for [http://codefu.com.au CodeFu].</div>
Steshaw
https://wiki.haskell.org/index.php?title=User:Steshaw&diff=37355
User:Steshaw
2010-10-30T01:56:02Z
<p>Steshaw: </p>
<hr />
<div>More at [http://steshaw.org/ steshaw.org].<br />
<br />
Steven Shaw</div>
Steshaw
https://wiki.haskell.org/index.php?title=User:Steshaw&diff=37354
User:Steshaw
2010-10-30T01:55:39Z
<p>Steshaw: </p>
<hr />
<div>More at [http://steshaw.org/].<br />
<br />
Steven Shaw</div>
Steshaw
https://wiki.haskell.org/index.php?title=New_monads&diff=36708
New monads
2010-09-07T23:10:30Z
<p>Steshaw: Link to wiki page on monadLib instead of old galios.com pages</p>
<hr />
<div>__TOC__<br />
<br />
Remember to add a [ [ Category:Code ] ] tag to any new sub-pages.<br />
<br />
== MonadBase ==<br />
<br />
It seems that the liftIO function from MonadIO can be generalized to access whatever the base of a transformer stack happens to be. So there is no need for a liftSTM, liftST, etc.<br />
<br />
View [[New monads/MonadBase]].<br />
<br />
== MonadLib ==<br />
<br />
[[MonadLib]] is written by Iavor S. Diatchki.<br />
<br />
It is a new version of the mtl package with base monads: Id, and Lift, and transformers ReaderT, WriterT, StateT, ExceptionT, ChoiceT, and ContT.<br />
<br />
It also defines BaseM which is like MonadBase above.<br />
<br />
== MonadRandom ==<br />
<br />
A simple monad transformer to allow computations in the transformed monad to generate random values.<br />
<br />
View [[New monads/MonadRandom]].<br />
<br />
===MonadRandomSplittable===<br />
A refinement of MonadRandom to integrate RandomGen's split function.<br />
<br />
View at [[New monads/MonadRandomSplittable]]<br />
<br />
== MaybeT ==<br />
<br />
The Maybe monad deserves a transformer, just like the other classic monads.<br />
<br />
View [[New monads/MaybeT]].<br />
<br />
== MonadSupply ==<br />
<br />
Here is a simple monad/monad transformer for computations which consume values from a (finite or infinite) supply. Note that due to pattern matching, running out of supply in a non-MonadZero monad will cause an error.<br />
<br />
View [[New monads/MonadSupply]].<br />
<br />
== MonadUndo ==<br />
<br />
Here is a modified state monad transformer for keeping track of undo/redo states automatically.<br />
<br />
View [[New monads/MonadUndo]].<br />
<br />
== MonadUnique ==<br />
<br />
This is a simple (trivial) monad transformer for supplying unique integer values to an algorithm.<br />
<br />
View [[New monads/MonadUnique]].<br />
<br />
== MonadSTO ==<br />
<br />
Here's an extension of the ST monad in which the references are ordered and showable (they list their creation index).<br />
<br />
View [[New monads/MonadSTO]].<br />
<br />
== MonadNondet ==<br />
<br />
There is a [[Sudoku#Monadic_Non-Deterministic_Solver | MonadNondet]] that when compiled with optimizations outperforms List.<br />
<br />
== Stateful nondeterminism ==<br />
<br />
There is a [[Stateful nondeterminism]] monad for if you want to do nondeterministic computation with local states for each of your threads and a global state shared by all your threads.<br />
<br />
== MonadAdvSTM ==<br />
<br />
Here is an extension of STM to easy interaction with IO after committing or retrying. Inspired by Simon P-J.<br />
<br />
View [[New monads/MonadAdvSTM]].<br />
<br />
== TimedStateT ==<br />
<br />
A monad transformer which combines State, Reader, and Error functionality to give the effect of a StateT monad which checks clock-time and stops the current computation if a period is exceeded.<br />
<br />
darcs get http://www.mapcar.org/haskell/TimedStateT/<br />
<br />
Haddocks: http://www.mapcar.org/haskell/TimedStateT/dist/doc/html/<br />
<br />
== MonadExit ==<br />
<br />
The Exit monad provides [[short-circuiting]] for complex program flow logic.<br />
<br />
If you are using CPS or MonadCont only for this purpose, the Exit monad will likely simplify your program considerably.<br />
<br />
View [[New monads/MonadExit|MonadExit]].<br />
<br />
== MonadSplit ==<br />
<br />
Represents the class of monads such that <br />
<br />
<haskell>l == (msplit l >>= \(x,xs) -> return x `mplus` xs)</haskell><br />
<br />
In English, msplit is a counterpart to "mplus".<br />
<br />
Using this, you can redefine many of the functions which previously depended on lists: foldM, scanM, inits, tails, and some derived functions.<br />
<br />
Note: A more general form of this monad,<br />
[http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Foldable.html Data.Foldable], is now part of the<br />
[http://haskell.org/ghc/docs/latest/html/libraries/ standard libraries].<br />
<br />
View [[New monads/MonadSplit]].<br />
<br />
== Lazy and Strict variants ==<br />
<br />
This section contains monads that have interesting Strict or Lazy properties.<br />
<br />
=== LazyWriterT ===<br />
<br />
This came up on the mailing list: Why is WriterT never lazy? The answer is it does not use lazy patterns with "~". So here is a more useful [[New monads/LazyWriterT]] that add two "~" to the definition of (>>=) and renames WriterT to LazyWriterT.<br />
<br />
=== Strict RWS ===<br />
<br />
This was contribute by John Meacham on on the haskell-cafe mailing list. [[New monads/UnboxedRWS]] is an strict variant of RWS.<br />
<br />
[[Category:Idioms]]<br />
[[Category:Monad]]<br />
[[Category:Proposals]]</div>
Steshaw