https://wiki.haskell.org/api.php?action=feedcontributions&user=ZiyaoWei&feedformat=atomHaskellWiki - User contributions [en]2022-08-07T22:01:04ZUser contributionsMediaWiki 1.31.7https://wiki.haskell.org/index.php?title=Monomorphism_restriction&diff=60347Monomorphism restriction2015-11-12T01:25:14Z<p>ZiyaoWei: </p>
<hr />
<div>The "monomorphism restriction" is a counter-intuitive rule in Haskell type inference. If you forget to provide a type signature, sometimes this rule will fill the free type variables with specific types using "type defaulting" rules. The resulting type signature is always less polymorphic than you'd expect, so often this results in the compiler throwing type errors at you in situations where you expected it to infer a perfectly sane type for a polymorphic expression.<br />
<br />
A simple example is <code>plus = (+)</code>. Without an explicit signature for <code>plus</code>, the compiler will not infer the type <code>(+) :: (Num a) => a -> a -> a</code> for `plus`, but will apply defaulting rules to specify <code>plus :: Integer -> Integer -> Integer</code>. When applied to <code>plus 3.5 2.7</code>, GHCi will then produce the somewhat-misleading-looking error, <code>No instance for (Fractional Integer) arising from the literal ‘3.5’</code>. <br />
<br />
The restriction is turned on by default in compiled modules, and turned off by default at the GHCi prompt (since GHC 7.8.1). You can override these defaults by using the MonomorphismRestriction and NoMonomorphismRestriction [[Language_Pragmas|language pragmas]].<br />
<br />
The exact definition of the restriction is fairly technical;<br />
it can be found in<br />
[http://www.haskell.org/onlinereport/haskell2010/haskellch4.html#x10-930004.5.5 section 4.5.5 of the Haskell 2010 Report].<br />
To a first approximation it means that you often cannot overload a function unless you provide an explicit type signature. In summary:<br />
<br />
<haskell><br />
-- This yields f1 :: (Show x) => x -> String<br />
f1 x = show x<br />
<br />
-- But this doesn't. Instead, f2 :: () -> String<br />
f2 = \x -> show x<br />
<br />
-- ...but we can fix that with an explicit type signature.<br />
f3 :: (Show a) => a -> String<br />
f3 = \x -> show x<br />
<br />
-- Similarly this produces () -> String<br />
f4 = show<br />
<br />
-- ...but this is allowed<br />
f5 :: (Show a) => a -> String<br />
f5 = show<br />
</haskell><br />
<br />
Arguably, these should all be equivalent, but thanks to the monomorphism restriction, they are not.<br />
<br />
The difference between the first and second version is that the first version binds x via a "function binding" (see<br />
[http://www.haskell.org/onlinereport/haskell2010/haskellch4.html#x10-830004.4.3 section 4.4.3 of the Haskell 2010 Report]),<br />
and is therefore unrestricted, but the second version does not. The reason why one is allowed and the other is not is that it's considered clear that sharing f1 will not share any computation, and less clear that sharing f2 will have the same effect. If this seems arbitrary, that's because it is. It is difficult to design an objective rule which disallows subjective unexpected behaviour. Some people are going to fall foul of the rule even though they're doing quite reasonable things.<br />
<br />
The monomorphism restriction is probably the most annoying and controversial feature of Haskell's type system.<br />
All seem to agree that it is evil - it is commonly called "The Dreaded Monomorphism Restriction" - but whether or not it is considered a necessary evil depends on who you ask.<br />
<br />
So why is the restriction imposed? The reasoning behind it is fairly subtle, and is fully explained in<br />
[http://www.haskell.org/onlinereport/haskell2010/haskellch4.html#x10-930004.5.5 section 4.5.5 of the Haskell 2010 Report].<br />
Basically, it solves one practical problem (without the restriction, there would be some ambiguous types) and one semantic problem (without the restriction, there would be some repeated evaluation where a programmer might expect the evaluation to be shared). Those who are for the restriction argue that these cases should be dealt with correctly. Those who are against the restriction argue that these cases are so rare that it's not worth sacrificing the<br />
type-independence of eta reduction.<br />
<br />
:An example, from [http://research.microsoft.com/~simonpj/papers/history-of-haskell/index.htm A History of Haskell]: Consider the <code>genericLength</code> function, from <code>Data.List</code><br />
<br />
:<haskell><br />
genericLength :: Num a => [b] -> a<br />
</haskell><br />
<br />
:And consider the function:<br />
<br />
<haskell><br />
f xs = (len,len)<br />
where<br />
len = genericLength xs<br />
</haskell><br />
<br />
:<code>len</code> has type <code>Num a => a</code> and, without the monomorphism restriction, it could be computed ''twice''. --[[User:ARG|ARG]]<br />
<br />
(This introductory section slightly expanded and re-arranged by [[User:YitzGale|YitzGale]].)<br />
<br />
----<br />
<br />
It is not clear to me how this whole thing about being computed once or twice works. Isn't type checking/inference something that happens at compile-time and shouldn't have any effect on what happens at run-time, as long as the typecheck passes? [[User:Dainichi|Dainichi]]<br />
<br />
The trouble is that typeclasses essentially introduce additional function parameters -- specifically, the dictionary of code implementing the instances in question. In the case of typeclass polymorphic pattern bindings, you end up turning something that looked like a pattern binding -- a constant that would only ever be evaluated once, into what is really a function binding, something which will not be memoised. [[User:CaleGibbard|CaleGibbard]] 23:46, 1 February 2008 (UTC)<br />
<br />
The type of <code>f</code>, if no signature is given, then the compiler doesn't know that the two elements of the returned pair are of the same type. It's return value will be:<br />
<br />
<haskell><br />
f::(Num a, Num b) => [x] -> (a, b)<br />
</haskell><br />
<br />
This means that <i>while compiling f</i> the compiler is unable to memoise len - clearly if a /= b then different code is executed to compute the first and second appearance of len in the pair. It's possible the compiler could do something more clever <i>when f is actually applied</i> if a == b, but I'm supposing this isn't a straight-forward thing to implement in the compilers. [[User:Dozer|Dozer]] 23:54, 4 February 2008 (GMT)<br />
<br />
Thank you, the nature of the ''problem'' is getting clearer now, but I'm still confused about how the restriction of top level definitions is supposed to ''solve'' this problem. To me, the given example explains why f's type is inferred to be <haskell>Num a => [x] -> (a, a)</haskell>, not <haskell>(Num a, Num b) => [x] -> (a, b)</haskell>, but not why this means that you cannot define top-level overloading outside pattern bindings. Is there an example which makes this clearer?<br />
<br />
Maybe I need to read up on the Hindley–Milner type system, but this seems related to the existence of functions (such as genericLength and read) that are polymorphic in their return type. Would MR need to exist without these functions? <br />
<br />
I'm a bit confused about functions like this, since I somehow feel they belong to more of a system with dependent types. <br />
<br />
--[[User:Dainichi|Dainichi]] 06:53 15 Aug 2011 (UTC)<br />
<br />
The following compiles for me on ghc 7.4.1:<br />
<br />
<haskell><br />
module Main where<br />
import Data.List<br />
<br />
main = putStrLn $ show (f [])<br />
<br />
f xs = (len,len)<br />
where<br />
len = genericLength xs<br />
</haskell><br />
<br />
If i add <code>f2 = \x -> show x</code>, compilation fails, demonstrating that i still have the monomorphism restriction enabled. <br />
<br />
This is not due to type inference from the putStrLn $ show (f []) doing anything; in fact, this compiles fine:<br />
<br />
<br />
<haskell><br />
module Main where<br />
import Data.List<br />
<br />
main = putStrLn ""<br />
<br />
f xs = (len,len)<br />
where<br />
len = genericLength xs<br />
<br />
-- f2 = \x -> show x <br />
</haskell><br />
<br />
whereas this fails to compile:<br />
<br />
<haskell><br />
module Main where<br />
import Data.List<br />
<br />
main = putStrLn ""<br />
<br />
--f xs = (len,len)<br />
-- where<br />
-- len = genericLength xs<br />
<br />
f2 = \x -> show x<br />
</haskell><br />
<br />
Why does the example from History of Haskell not fail? -- [[BayleShanks]] <br />
<br />
<br />
----<br />
<br />
Oversimplifying the debate somewhat: Those in favour tend to be those who have written Haskell [[Implementations]] and those against tend to be those who have written complex combinator libraries (and hence have hit their collective heads against the restriction all too often). It often boils down to the fact that programmers want to avoid [http://catb.org/esr/jargon/html/L/legalese.html legalese], and language implementors want to avoid [http://catb.org/esr/jargon/html/C/cruft.html cruft].<br />
<br />
In almost all cases, you can get around the restriction by including explicit type declarations. Those who are for the restriction are usually quick to point out that including explicit type declarations is good programming practice anyway. In a few very rare cases, however, you may need to supply a type signature which is not valid Haskell. (Such type signatures require a type system extension such as [[Scoped type variables]].) Unless you're writing some weird combinator libraries, or are in the habit of not writing type declarations, you're unlikely to come across it. Even so, most Haskell [[Implementations]] provide a way to turn the restriction off.<br />
<br />
See also: [http://haskell.org/onlinereport/decls.html#sect4.5.5 Section 4.5.5, Haskell 98 report].<br />
<br />
-- [[Andrew Bromage]]<br />
<br />
Some question or suggestion: As I understand the problem arises from the situation that two different forms of assignment are described by the same notation. There are two forms of assignment, namely the inspection of data structures ("unpacking", "pattern binding") and the definition of functions ("function binding"). Unique examples are:<br />
<br />
<haskell><br />
let f x = y -- function definition<br />
let F x = y -- data structure decomposition<br />
</haskell><br />
<br />
In the first case we have the identifier f starting with lower case. This means this is a function binding. The second assignment starts with F, which must be a constructor. That's why this is a pattern binding. The monomorphism restriction applies only to the pattern binding. I think this was not defined in order to please compiler writers, but has shown to be useful in practice, or am I wrong? But the different handling of these binding types leads to a problem since both types have a common case.<br />
<br />
<haskell><br />
let x = y -- function or pattern binding?<br />
</haskell><br />
<br />
So, what speaks against differentiating the assignments notationally, say<br />
<br />
<haskell><br />
let f x = y -- function definition<br />
let F x <= y -- data structure decomposition<br />
</haskell><br />
<br />
and keep the monomorphism restriction as it is?<br />
<br />
-- [[Henning Thielemann]]<br />
<br />
The problem isn't just pattern bindings, it's that pattern bindings which are typeclass polymorphic are actually function bindings in disguise, since the usual implementation of typeclasses adds parameters to such definitions, to allow the definition to take the typeclass dictionaries involved. Thus, such pattern bindings have different properties with respect to sharing (they're generally less shared than you want). In especially bad cases, without the MR, it is possible to have programs which run exponentially slower without type signatures than when signatures are added. Just distinguishing pattern bindings with a new notation doesn't solve the problem, since they'll have to be converted into function bindings in that case anyway. If you intend to keep the MR, then you don't need to change anything. The issue with the MR is just the fact that it's annoying to have eta-reduction fail in the absence of explicit type signatures, and the fact that it makes otherwise perfectly valid programs fail to compile on speculation that there might be loss of sharing (when there usually isn't, or at least the impact isn't large enough to worry about).<br />
<br />
John Hughes recently advocated the removal of the MR on the Haskell Prime mailing list, and suggested replacing it with two forms of pattern binding: one for call-by-name (polymorphic, not shared), and one for call-by-need (monomorphic, guaranteed shared). This might be similar to what you're suggesting. If you look at it too closely, it seems like a good solution, but the overall impact on Haskell code seems too large to me, to resolve a distinction which it ought to be statically possible to determine.<br />
<br />
I'm of the opinion that it would be better to find a way to restore sharing lost through the typeclass transformation in some way, or else implement typeclasses in an altogether different way which doesn't run into this problem. Additional runtime machinery seems like a likely candidate for this -- the interactions with garbage collection are somewhat subtle, but I think it should be doable. It's also possible to restore the sharing via whole-program analysis, but advocates of separate compilation will probably complain, unless we were to find a mechanism to fix the problem from the object code (and potentially temporaries) at link time.<br />
<br />
:- [[Cale Gibbard]]<br />
<br />
--------------------<br />
I think it'd be useful to collect a set of examples of the Monormorphism Restriction biting people in an unexpected way. This may help to inform the debate over the MR by giving real-life examples. Add more examples here if (an only if) they constitute an unexpected MR-related incident in your life or someone else's. No invented examples! -- [[Simon Peyton Jones]]<br />
<br />
* GHC Trac bug [http://hackage.haskell.org/trac/ghc/ticket/1749 1749]<br />
* In trying to build an editor with undoable actions:<br />
<haskell><br />
class EditAction e a | e -> a where<br />
apply :: a -> e -> a<br />
<br />
data ListAction a = Append a | Remove<br />
<br />
instance EditAction (ListAction a) [a] where<br />
apply list (Append a) = a:list<br />
apply (x:xs) Remove = xs<br />
<br />
-- Apply all the EditActions to the input<br />
--edit :: EditAction e a => a -> [e] -> a -- monomorphism restriction - I have to put this in!<br />
edit = foldl apply<br />
</haskell><br />
<br />
----<br />
Back before forM was in the Control.Monad library, I once spent about 1/2 an hour trying to figure out why my action in the ST monad was having its '<hask>s</hask>' parameter squished to <hask>()</hask>. I tore the code apart for quite a while before discovering that it was that the MR was applying to my definition of <hask>forM</hask>:<br />
<br />
<haskell><br />
forM = flip mapM<br />
</haskell><br />
<br />
----<br />
I recently got tired of typing <hask>print "blah"</hask> in a ghci shell session and tried <hask>let p = print</hask>. Thanks to MR and Haskell defaulting, the type of <hask>p</hask> silently became <hask>() -> IO ()</hask>. No surprise that my new "short" version of print was only capable of printing void values -<br />
<br />
<hask><br />
Prelude> p ()<br />
()<br />
Prelude> p "blah"<br />
<br />
<interactive>:1:2:<br />
Couldn't match expected type `()' against inferred type `[Char]'<br />
In the first argument of `p', namely `"blah"'<br />
In the expression: p "blah"<br />
In the definition of `it': it = p "blah"<br />
</hask><br />
<br />
----<br />
<br />
<haskell><br />
import Graphics.UI.Gtk<br />
import Graphics.UI.Gtk.Glade<br />
<br />
-- xmlGetWidget' :: WidgetClass widget => (GObject -> widget) -> String -> IO widget<br />
xmlGetWidget' = xmlGetWidget undefined<br />
<br />
main :: IO ()<br />
main<br />
= do<br />
initGUI<br />
window <- xmlGetWidget' castToWindow "window1"<br />
button <- xmlGetWidget' castToButton "button1"<br />
widgetShowAll window<br />
mainGUI<br />
</haskell><br />
<br />
If I comment main, I cannot compile this code because of the monomorphism restriction. With main, it'll infer the type:<br />
<br />
<haskell><br />
xmlGetWidget' :: (GObject -> Window) -> String -> IO Window<br />
</haskell><br />
<br />
And give me a type error in the button line. If I uncomment the type signature, it'll work.<br />
----<br />
<br />
I wasn't expecting the following to fail...<br />
<br />
<haskell><br />
square :: (Num a) => a -> a <br />
square x = x * x <br />
dx = 0.0000001<br />
deriv1 :: (Fractional a) => (a -> a) -> (a -> a)<br />
deriv1 g = (\x -> ((g (x + 2) - (g x)) / dx )) <br />
main = printf "res==%g %g\n" (square 5.12::Double) ((deriv1 square) 2::Float)<br />
</haskell><br />
<br />
and for this to work.<br />
<br />
<haskell><br />
square :: (Num a) => a -> a <br />
square x = x * x <br />
dx = 0.0000001<br />
deriv1 :: (Fractional a) => (a -> a) -> (a -> a)<br />
deriv1 g = (\x -> ((g (x + 2) - (g x)) / 0.0000001 )) <br />
main = printf "res==%g %g\n" (square 5.12::Double) ((deriv1 square) 2::Float)<br />
</haskell><br />
<br />
The fix was to add<br />
<br />
<haskell><br />
dx :: Fractional a => a<br />
</haskell><br />
<br />
--Harry<br />
<br />
----<br />
<br />
Along the same lines as Simon's question above, does anyone have any real examples of being bitten by the lack of MR? I know what it's for, but I can't really think of any realistic cases when it would be a problem. --pumpkin<br />
<br />
----<br />
<br />
I tried to define foldl in terms of foldr, and discovered<br />
<br />
<haskell><br />
foldl' = foldr (\x y -> (\a h -> y (h a x) h)) const<br />
</haskell><br />
<br />
doesn't typecheck while<br />
<br />
<haskell><br />
foldl' xs v f = foldr (\x y -> (\a h -> y (h a x) h)) const xs v f<br />
</haskell><br />
<br />
does. Spent a solid couple hours trying to find where my derivation went wrong before accidentally stumbled upon the solution. -- wzy<br />
<br />
[[Category:Glossary]]<br />
[[Category:Language]]</div>ZiyaoWeihttps://wiki.haskell.org/index.php?title=Embedded_domain_specific_language&diff=60281Embedded domain specific language2015-10-22T16:11:22Z<p>ZiyaoWei: Update dead link</p>
<hr />
<div>'''Embedded Domain Specific Language''' means that you embed a [http://en.wikipedia.org/wiki/Domain_specific_language Domain specific language] in a language like Haskell.<br />
E.g. using the [http://cryp.to/funcmp/ Functional MetaPost library] you can write Haskell expressions, which are then translated to MetaPost, MetaPost is run on the generated code and the result of MetaPost can be post-processed in Haskell.<br />
<br />
<br />
== Degree of embedding ==<br />
<br />
There are two major degrees of embedding:<br />
<br />
* Shallow embedding: All Haskell operations immediately translate to the target language. E.g. the Haskell expression <hask>a+b</hask> is translated to a <hask>String</hask> like <hask>"a + b"</hask> containing that target language expression.<br />
* Deep embedding: Haskell operations only build an interim Haskell data structure that reflects the expression tree. E.g. the Haskell expression <hask>a+b</hask> is translated to the Haskell data structure <hask>Add (Var "a") (Var "b")</hask>. This structure allows transformations like optimizations before translating to the target language.<br />
<br />
<br />
== Discussion of common problems ==<br />
<br />
[[Sharing]] and [http://en.wikipedia.org/wiki/Recursion recursion] are common problems when implementing DSLs.<br />
Often some kind of [[observable sharing]] is requested<br />
that requires a deep embedding.<br />
<br />
* Oleg in Haskell-Cafe about [http://www.haskell.org/pipermail/haskell-cafe/2008-February/039639.html Designing DSL with explicit sharing (was: I love purity, but it's killing me)]<br />
* Koen Classen: [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.4053 Observable Sharing for Functional Circuit Description]<br />
* Andy Gill: [http://www.ittc.ku.edu/~andygill/papers/reifyGraph.pdf Type-Safe Observable Sharing]<br />
* Tom Lokhorst [http://tom.lokhorst.eu/2010/02/awesomeprelude-presentation-video AwesomePrelude presentation (video)]<br />
* Leandro Lisboa Penz [http://www.lpenz.org/articles/hedsl-sharedexpenses/ Haskell eDSL Tutorial - Shared expenses]<br />
* Bruno Oliveira and William Cook: [http://www.cs.utexas.edu/~wcook/Drafts/2012/graphs.pdf Functional Programming with Structured Graphs]<br />
* Emil Axelsson and Koen Claessen: [http://www.cse.chalmers.se/~emax/documents/axelsson2013using.pdf Using Circular Programs for Higher-Order Syntax]<br />
* Oleg Kiselyov: [http://okmij.org/ftp/tagless-final/sharing/sharing.pdf Implementing explicit and finding implicit sharing in embedded DSLs]<br />
<br />
== Examples of Domain Specific Languages ==<br />
<br />
* Functional MetaPost ({{HackagePackage|id=funcmp}}) is a Haskell frontend to the MetaPost language by John Hobby. Users write their graphics as Haskell programs, which then emit MetaPost code that can be compiled into encapsulated PostScript files and smoothly included into e.g. LaTeX.<br />
<br />
* {{HackagePackage|id=orc}}: Orchestration-style coordination EDSL<br />
<br />
* {{HackagePackage|id=synthesizer-llvm}} provides [[Synthesizer|audio signal processing functions]] that are translated to [[LLVM]] assembly language. This warrants very fast computation. It uses shallow embedding.<br />
<br />
* The {{HackagePackage|id=diagrams-cairo}} package. A full-featured backend for rendering diagrams using the cairo rendering engine. To get started, see Diagrams.Backend.Cairo.CmdLine.<br />
<br />
* {{HackagePackage|id=Workflow}}: library for transparent execution of interruptible computations<br />
<br />
* [http://www.yesodweb.com/book/templates#file253-synopsis Hamlet, Julius, Cassius and Lucius] are languages embedded in the [http://www.yesodweb.com/ Yesod framework]<br />
<br />
== More to read/view ==<br />
<br />
* [http://cacm.acm.org/magazines/2011/7/109910-dsl-for-the-uninitiated/fulltext DSL for the Uninitiated], an introduction to DSLs, not Haskell-specific<br />
* [http://skillsmatter.com/podcast/scala/haskell-for-embedded-domain-specific-languages Haskell for embedded domain-specific languages] (podcast)<br />
* [[Research papers/Domain specific languages]]<br />
* [http://donsbot.wordpress.com/2007/03/10/practical-haskell-shell-scripting-with-error-handling-and-privilege-separation/ Practical Haskell: shell scripting with error handling and privilege separation] (blog article)<br />
* [http://www.reddit.com/r/haskell/comments/2e8d53/whats_the_best_practice_for_building_a_dsl_in/ What's the best practice for building a DSL in haskell?], a discussion at Reddit<br />
<br />
<br />
[[Category:Glossary]]</div>ZiyaoWeihttps://wiki.haskell.org/index.php?title=Research_papers/Authors&diff=60183Research papers/Authors2015-10-03T17:21:27Z<p>ZiyaoWei: Delete dupe entry of Graham Hutton</p>
<hr />
<div>__NOTOC__<br />
<br />
==A==<br />
*[http://www2.tcs.ifi.lmu.de/~abel/ Andres Abel]<br />
*[http://www.cs.nott.ac.uk/~txa/publ/ Thorsten Altenkirch]<br />
*[http://homepages.cwi.nl/~atanasso/pub Frank Atanassow]<br />
*[http://www.cs.chalmers.se/~augustss/ Lennart Augustsson]<br />
<br />
==B==<br />
*[http://www.cs.uu.nl/groups/ST/stbib/baars-by-year/baars-by-year-by-year.html Arthur Baars]<br />
*[http://web.comlab.ox.ac.uk/oucl/work/richard.bird/publications.html Richard Bird]<br />
*[http://www.cs.chalmers.se/~bjesse/ Per Bjesse]<br />
*[http://www.cs.chalmers.se/~boquist/ Urban Boquist]<br />
*[http://www.dcs.gla.ac.uk/~bunkenba/ Alex Bunkenburg]<br />
*[http://www.cs.sfu.ca/people/Faculty/Burton/publications.html F. Warren Burton]<br />
*[http://www.cs.st-andrews.ac.uk/~chrisb/ Christopher Brown]<br />
<br />
==C==<br />
*[http://www.cse.ogi.edu/~magnus/ Magnus Carlsson]<br />
*[http://www.cse.unsw.edu.au/~chak/papers/papers.html Manuel M. T. Chakravarty]<br />
*[http://www.cs.kent.ac.uk/people/staff/oc/pubs.html Olaf Chitil]<br />
*[http://www.iis.sinica.edu.tw/~trc/node2.html Tyng-Ruey Chuang]<br />
*[http://www.cs.chalmers.se/~koen/pubs/ Koen Claessen]<br />
*[http://www.dcs.gla.ac.uk/~grmc/ Graham Collins]<br />
*[http://www.irisa.fr/EXTERNE/projet/lande/consel/consel.html Charles Consel]<br />
*[http://www.apocalypse.org/pub/u/antony/work/index.html Antony Courtney]<br />
<br />
==D==<br />
*[http://www.c3.lanl.gov/~kei/publications.html Kei Davis]<br />
*[http://www.cse.ogi.edu/~diatchki/papers/ Iavor Diatchki]<br />
<br />
==E==<br />
*[http://conal.net/papers/ Conal Elliott]<br />
*[http://www.cambridge.intel-research.net/~rennals/ Robert Ennals]<br />
*[http://web.engr.oregonstate.edu/~erwig/papers/ Martin Erwig]<br />
<br />
==F==<br />
*[http://web.it.kth.se/~kff/publications.html Karl-Filip Fax&eacute;n]<br />
*[http://yeats.ucc.ie/~abf/ Alex Ferguson]<br />
*[http://www.galois.com/~sof/pubs.html Sigbjorn Finne]<br />
*[http://www.cs.uu.nl/people/jeroen/ Jeroen Fokker]<br />
<br />
==G==<br />
*[http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/ Jeremy Gibbons]<br />
*[http://www.monadgarden.com/andy/ Andy Gill]<br />
*[http://www.dcs.gla.ac.uk/~joy/ Joy Goodman]<br />
*[http://research.microsoft.com/~adg/ Andrew D. Gordon]<br />
*Louis-Julien Guillemette<br />
*[http://www.cs.chalmers.se/~gustavss/ J&ouml;rgen Gustavsson]<br />
<br />
==H==<br />
*[http://www.dcs.gla.ac.uk/~cvh/ Cordelia Hall]<br />
*[http://www.cse.ogi.edu/~hallgren/ Thomas Hallgren]<br />
*[http://www-fp.dcs.st-and.ac.uk/~kh/papers/ABSTRACTS.html Kevin Hammond]<br />
*[http://research.microsoft.com/~tharris/ Tim Harris]<br />
*[http://www.cs.uu.nl/~bastiaan/ Bastiaan Heeren]<br />
*[http://www.cs.chalmers.se/~heldal/ Rogardt Heldal]<br />
*[http://www.cs.unc.edu/~heringto/ Dean Herington]<br />
*[http://www.infosun.fmi.uni-passau.de/cl/staff/herrmann/index.html Christoph A. Herrmann]<br />
*[http://www.informatik.uni-bonn.de/~ralf/publications/ Ralf Hinze]<br />
*[http://www.cs.uu.nl/people/stefan Stefan Holdermans]<br />
*[http://www.cse.ogi.edu/~hook/new/Default.htm James Hook]<br />
*[http://www.ipl.t.u-tokyo.ac.jp/~hu/pub/tech.html Zhenjiang Hu]<br />
*[http://cs-www.cs.yale.edu/homes/hudak.html Paul Hudak]<br />
*[http://www.cs.chalmers.se/~rjmh/pubs.htm John Hughes]<br />
*[http://www.cs.nott.ac.uk/~gmh/ Graham Hutton]<br />
<br />
==I==<br />
*[http://www.cs.uu.nl/groups/ST/stbib/ijzendoorn-by-year/ijzendoorn-by-year-by-year.html Arjan van IJzendoorn]<br />
*[http://www.cs.chalmers.se/~indrika/ Mia Indrika]<br />
<br />
==J==<br />
*[http://www.cs.chalmers.se/~patrikj/ Patrik Jansson]<br />
*[http://www.cs.uu.nl/groups/ST/stbib/jeuring-by-year/jeuring-by-year-by-year.html Johan Jeuring]<br />
*[http://crab.rutgers.edu/~pjohann/vita.html Patricia Johann]<br />
*[http://www.cs.chalmers.se/~bengtj/ Bengt Johansson]<br />
*[http://www.cs.chalmers.se/~johnsson Thomas Johnsson]<br />
*[http://web.cecs.pdx.edu/~mpj/pubs.html Mark P. Jones]<br />
*[http://www.cs.stir.ac.uk/~sbj/ Simon B. Jones]<br />
*[http://research.microsoft.com/Users/simonpj Simon Peyton Jones]<br />
*[http://www.syntaxpolice.org/ Isaac Jones]<br />
<br />
==K==<br />
*[http://users.info.unicaen.fr/~karczma Jerzy Karczmarczuk]<br />
*[http://www.cse.unsw.edu.au/~keller/#publications Gabriele Keller]<br />
*[http://okmij.org/ftp/ Oleg Kiselyov]<br />
*[http://www.cse.ogi.edu/~krstic/ Sava Krstic]<br />
<br />
==L==<br />
*[http://lsi.uniovi.es/~labra Jose E. Labra]<br />
*[http://homepages.cwi.nl/~ralf/publications.html Ralf Lämmel]<br />
*[http://www.cse.ogi.edu/~jl John Launchbury]<br />
*[http://www.cs.uu.nl/~daan/pubs.html Daan Leijen]<br />
*[http://www.cse.ogi.edu/~jlewis Jeff Lewis]<br />
*[http://www.seas.upenn.edu/~lipeng/homepage/ Peng Li]<br />
*[http://java.sun.com/people/sl/ Sheng Liang]<br />
*[http://www.iai.uni-bonn.de/~loeh Andres L&ouml;h]<br />
*[http://www.dcs.gla.ac.uk/~hwloidl/ Hans-Wolfgang Loidl]<br />
*[http://www.mathematik.uni-marburg.de/~loogen Rita Loogen]<br />
*[http://www.frogsonice.com/work.html Sandra J. Loosemore]<br />
*[http://web.comlab.ox.ac.uk/oucl/work/ian.lynagh/papers/ Ian Lynagh]<br />
<br />
==M==<br />
*[http://www.haskell.org/~simonmar/bib/bib.html Simon Marlow] <br />
*[http://personal.cis.strath.ac.uk/~conor/pub/ Conor McBride]<br />
*[http://www.dcs.st-andrews.ac.uk/~james/ James McKinna]<br />
*[http://www.kestrel.edu/home/people/meertens/ Lambert Meertens]<br />
*[http://research.microsoft.com/~emeijer/ Eric Meijer]<br />
*[http://www.engr.uconn.edu/~jeffm/ Jeff Meunier]<br />
*[http://www-users.cs.york.ac.uk/~ndm/downloads.php Neil Mitchell]<br />
*[http://www.disi.unige.it/person/MoggiE/publications.html Eugenio Moggi]<br />
*Andrew Moran<br />
*Stefan Monnier<br />
<br />
==N==<br />
*[http://cs-www.cs.yale.edu/homes/nilsson/papers.html Henrik Nilsson]<br />
*[http://www.cse.ogi.edu/~nordin Thomas Nordin]<br />
*[http://www.cse.ogi.edu/~nordland/ Johan Nordlander]<br />
<br />
==O==<br />
*[http://lampwww.epfl.ch/~odersky/papers/ Martin Odersky]<br />
*[http://www.dcs.gla.ac.uk/~jtod/ John O'Donnell]<br />
*[http://www.eecs.usma.edu/Personnel/okasaki Chris Okasaki]<br />
*[http://www.ipl.t.u-tokyo.ac.jp/~onoue/ Yoshiyuki Onoue]<br />
<br />
==P==<br />
*[http://www.cs.chalmers.se/~pareto/ Lars Pareto]<br />
*[http://www.dcs.gla.ac.uk/~partain/ Will Partain]<br />
*[http://www.soi.city.ac.uk/~ross/papers/ Ross Paterson]<br />
*[[User:John Peterson|John Peterson]]<br />
*[http://research.microsoft.com/Users/simonpj Simon Peyton Jones]<br />
*[http://www.cs.mu.oz.au/~bjpop/papers.html Bernie Pope]<br />
*[http://www.mathematik.uni-marburg.de/~priebe Steffen Priebe]<br />
*[http://ad-astra.ro/Ha$kell Popa Dan <br> Public e-mail: popavdan@yahoo.com]<br />
<br />
==Q==<br />
<br />
==R==<br />
*[http://www.reid-consulting-uk.ltd.uk/alastair/ Alastair Reid]<br />
*[http://www.dcs.gla.ac.uk/~reidrm/ Richard Reid]<br />
*[http://www.dcs.gla.ac.uk/~reig/ Fermin Reig]<br />
*[http://www-users.cs.york.ac.uk/~colin/ Colin Runciman]<br />
<br />
==S==<br />
*[http://www.cs.chalmers.se/~andrei/ Andrei Sabelfeld]<br />
*[http://www.dcs.gla.ac.uk/~meurig/ Meurig Sage]<br />
*[http://www.cs.chalmers.se/~dave/ David Sands]<br />
*[http://www.dcs.gla.ac.uk/~sansom/ Patrick Sansom]<br />
*[http://www.di.ufpe.br/~alms/ Andr&eacute; Santos]<br />
*[http://users.ugent.be/~tschrijv/ Tom Schrijvers]<br />
*[http://www.cse.unsw.edu.au/~sseefried/papers/papers.html Sean Seefried]<br />
*[http://web.cecs.pdx.edu/~sheard/papers/ Tim Sheard]<br />
*[http://www.cs.chalmers.se/~ms/ Mary Sheeran]<br />
*[http://www.cse.ogi.edu/~mbs/ Mark Shields]<br />
*[http://www.dis.strath.ac.uk/people/sinclair/ Duncan Sinclair]<br />
*[http://research.microsoft.com/en-us/people/satnams/ Satnam Singh]<br />
*[http://www.cs.chalmers.se/~sparud/ Jan Sparud]<br />
*[http://www.cs.bris.ac.uk/~spilio/ Eleni Spiliopoulou]<br />
*[http://www.cse.unsw.edu.au/~dons/papers.html Don Stewart]<br />
*[http://ww2.cs.mu.oz.au/~sulzmann/ Martin Sulzmann]<br />
*[http://www.cse.chalmers.se/~josefs/ Josef Svenningsson]<br />
*[http://www.cs.uu.nl/groups/ST/stbib/swierstra-by-year/swierstra-by-year-by-year.html Doaitse Swierstra]<br />
<br />
==T==<br />
*[http://www.cs.chalmers.se/~makoto Makoto Takeyama]<br />
*[http://www.henning-thielemann.de/ResearchE.html Henning Thielemann]<br />
*[http://www.cs.kent.ac.uk/people/staff/sjt/pubs.html Simon Thompson]<br />
*[http://www.cs.york.ac.uk/~mjt/ Michael Thyer]<br />
*[http://www.macs.hw.ac.uk/~trinder/publications.html Paul Trinder]<br />
*[http://www.cs.yale.edu/homes/tullsen/publications.html Mark Tullsen]<br />
<br />
==U==<br />
<br />
* [http://www.cs.ioc.ee/~tarmo/papers/ Tarmo Uustalu]<br />
<br />
==V==<br />
* [http://www.cs.ru.nl/A.vanWeelden/index.php?p=publications Arjen van Weelden]<br />
* [http://www.cs.ut.ee/~varmo/papers/index.html Varmo Vene]<br />
* [http://www.iai.uni-bonn.de/~jv/ Janis Voigtländer]<br />
<br />
==W==<br />
*[http://homepages.inf.ed.ac.uk/wadler/ Philip Wadler]<br />
*[http://www.imn.htwk-leipzig.de/~waldmann/ Johannes Waldmann]<br />
*[ftp://ftp.cs.york.ac.uk/pub/malcolm/ Malcolm Wallace]<br />
*[http://www.lochan.org/keith/publications/index.html Keith Wansbrough]<br />
*[http://www.cis.upenn.edu/~geoffw/research/index.html Geoff Washburn]<br />
*[http://www.seas.upenn.edu/%7Esweirich/publications.html Stephanie Weirich]<br />
*[http://www.informatik.uni-freiburg.de/~wehr/#Publications Stefan Wehr]<br />
*[http://www.lotus.com/lotus/research.nsf/grouppage?Openpage Eric Wilcox]<br />
*[http://www.dcs.gla.ac.uk/~nww/ Noel Winstanley]<br />
<br />
==X==<br />
*[http://www.cl.cam.ac.uk/~nx200/ Dana Xu]<br />
<br />
==Y==<br />
<br />
==Z==<br />
<br />
<i>Authors, please add yourself! :)</i></div>ZiyaoWeihttps://wiki.haskell.org/index.php?title=99_questions/Solutions/82&diff=4467099 questions/Solutions/822012-02-25T04:14:32Z<p>ZiyaoWei: Solution to Problem 82 using list comprehension added</p>
<hr />
<div>Brute-force search from the source, using list comprehension:<br />
import Data.List (partition)<br />
cycle' :: Int -> [(Int, Int)] -> [ [Int] ]<br />
cycle' n g = search [[n]] []<br />
where search [] result = result<br />
search cur result = search (go active) (arrive ++ result)<br />
where split = partition end cur<br />
end s = (last s == n) && (length s /= 1)<br />
active = snd split<br />
arrive = fst split<br />
go ls = [ x ++ [snd y] | x <- ls, y <- g, last x == fst y, not (snd y `elem` tail x)]</div>ZiyaoWei