https://wiki.haskell.org/api.php?action=feedcontributions&user=Brecknell&feedformat=atomHaskellWiki - User contributions [en]2015-08-03T10:22:07ZUser contributionsMediaWiki 1.19.14+dfsg-1https://wiki.haskell.org/OzHaskellOzHaskell2007-10-28T07:21:33Z<p>Brecknell: </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]]<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]]<br />
* [[:User:ivanm|Ivan Miljenovic]] (Brisbane)<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 />
(Add your name!)<br />
<br />
== Possible dates ==<br />
<br />
Shall we try to organise something for sometime over the summer? Avoiding the summer holidays, either of the following two periods seem attractive:<br />
<br />
* last week of November/first week of December or<br />
* last week of January/first week of February.<br />
<br />
(Add any additional periods that you would find attractive and/or comment on suitability.)<br />
<br />
Events to avoid clashing with:<br />
<br />
* The 2007 federal election (weekend of 24-25 November).<br />
* linux.conf.au (28 Jan - 2 Feb 2007, unless it's held in conjunction).<br />
* Inevitable family Christmas parties/holiday travel rush (some weekends in December, different for everyone I suspect).<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 />
* Manuel Chakravarty: ''Type-level Programming with Type Families''<br />
::GHC recently gained support for data families and type synonym families (which are a generalisation of our earlier proposal for associated types). In this talk, I'd give an overview over this new language feature, illustrate what it is good for, and discuss why I believe it fits Haskell better than functional dependencies.<br />
* Bernie Pope: ''The GHCi debugger''<br />
:: A new breakpoint debugger has been added to GHCi. In this talk, I'd demonstrate how to use the debugger, and also go into some detail about how it works. I might even discuss the relative advantages and disadvantages of this debugger over tools such as Hat.<br />
<br />
=== Demo proposals ===</div>Brecknellhttps://wiki.haskell.org/OzHaskellOzHaskell2007-09-17T03:35:41Z<p>Brecknell: </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]]<br />
* [[:User:TonyMorris|Tony Morris]]<br />
* [[:User:Brecknell|Matthew Brecknell]] (Brisbane)</div>Brecknellhttps://wiki.haskell.org/Euler_problems/91_to_100Euler problems/91 to 1002007-08-31T11:38:26Z<p>Brecknell: Euler problem 91</p>
<hr />
<div>[[Category:Programming exercise spoilers]]<br />
== [http://projecteuler.net/index.php?section=view&id=91 Problem 91] ==<br />
Find the number of right angle triangles in the quadrant.<br />
<br />
Solution:<br />
<haskell><br />
reduce x y = (quot x d, quot y d)<br />
where d = gcd x y<br />
<br />
problem_91 n = 3*n*n + 2* sum others<br />
where<br />
others = do<br />
x1 <- [1..n]<br />
y1 <- [1..n]<br />
let (yi,xi) = reduce x1 y1<br />
let yc = quot (n-y1) yi<br />
let xc = quot x1 xi<br />
return (min xc yc)<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=92 Problem 92] ==<br />
Investigating a square digits number chain with a surprising property.<br />
<br />
Solution:<br />
<haskell><br />
problem_92 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=93 Problem 93] ==<br />
Using four distinct digits and the rules of arithmetic, find the longest sequence of target numbers.<br />
<br />
Solution:<br />
<haskell><br />
problem_93 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=94 Problem 94] ==<br />
Investigating almost equilateral triangles with integral sides and area.<br />
<br />
Solution:<br />
<haskell><br />
problem_94 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=95 Problem 95] ==<br />
Find the smallest member of the longest amicable chain with no element exceeding one million.<br />
<br />
Solution which avoid visiting a number more than one time :<br />
<haskell><br />
import Data.Array.Unboxed<br />
import qualified Data.IntSet as S<br />
import Data.List<br />
<br />
takeUntil _ [] = []<br />
takeUntil pred (x:xs) = x : if pred x then takeUntil pred xs else []<br />
<br />
chain n s = lgo [n] $ properDivisorsSum ! n<br />
where lgo xs x | x > 1000000 || S.notMember x s = (xs,[])<br />
| x `elem` xs = (xs,x : takeUntil (/= x) xs)<br />
| otherwise = lgo (x:xs) $ properDivisorsSum ! x<br />
<br />
properDivisorsSum :: UArray Int Int<br />
properDivisorsSum = accumArray (+) 1 (0,1000000) <br />
$ (0,-1):[(k,factor)| <br />
factor<-[2..1000000 `div` 2]<br />
, k<-[2*factor,2*factor+factor..1000000]<br />
]<br />
<br />
base = S.fromList [1..1000000]<br />
<br />
problem_95 = fst $ until (S.null . snd) f ((0,0),base)<br />
where <br />
f (p@(n,m), s) = (p', s')<br />
where <br />
setMin = head $ S.toAscList s<br />
(explored, chn) = chain setMin s<br />
len = length chn<br />
p' = if len > m then (minimum chn, len) else p<br />
s' = foldl' (flip S.delete) s explored<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=96 Problem 96] ==<br />
Devise an algorithm for solving Su Doku puzzles.<br />
<br />
Solution:<br />
<haskell><br />
problem_96 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=97 Problem 97] ==<br />
Find the last ten digits of the non-Mersenne prime: 28433 × 2<sup>7830457</sup> + 1.<br />
<br />
Solution:<br />
<haskell><br />
problem_97 = (28433 * 2^7830457 + 1) `mod` (10^10)<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=98 Problem 98] ==<br />
Investigating words, and their anagrams, which can represent square numbers.<br />
<br />
Solution:<br />
<haskell><br />
problem_98 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=99 Problem 99] ==<br />
Which base/exponent pair in the file has the greatest numerical value?<br />
<br />
Solution:<br />
<haskell><br />
problem_99 = undefined<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=100 Problem 100] ==<br />
Finding the number of blue discs for which there is 50% chance of taking two blue.<br />
<br />
Solution:<br />
<haskell><br />
problem_100 = undefined<br />
</haskell><br />
<br />
[[Category:Tutorials]]<br />
[[Category:Code]]</div>Brecknellhttps://wiki.haskell.org/Talk:SantaClausProblemV2Talk:SantaClausProblemV22007-01-11T14:32:49Z<p>Brecknell: </p>
<hr />
<div>= Beautiful concurrency =<br />
<br />
I am writing a chapter for a book called "Beautiful code", edited by Greg Wilson. The chapter is a tutorial about Software Transactional Memory in Haskell.<br />
<br />
After a lot of useful feedback, I have now completed [http://research.microsoft.com/~simonpj/papers/stm/beautiful.ps Version 2] of the paper. The [http://research.microsoft.com/~simonpj/papers/stm/Santa.hs.gz Haskell code] is also available.<br />
<br />
I would welcome any comments or questions you have on the paper, or constructive suggestions for improving it; the more concrete the better. You can see what people said about version 1 on the version 1 talk page: [[Talk:SantaClausProblem ]].<br />
<br />
The book is aimed at a general audience of programmers, <em>not</em> Haskell geeks, so I have tried to explain everything necessary as I go along. So if you are not a Haskell expert, your input would be particularly valuable to me.<br />
<br />
You can email me directly (simonpj@microsoft.com), or add Wiki talk notes below.<br />
<br />
If you give your real name somewhere in your text (or email it to me), I'll add you to the acknowledgements at the end of the chapter. Notably, I'd like to acknowledge Steven807, Tibbe, Fanf, Garious, Rycee, Brecknell, Mvanier, Gaal, Fernando, Gknauth, EngineerScotty, BoAdler.<br />
<br />
----------<br />
<br />
[[User:Simonpj|Simonpj]] 14:26, 22 December 2006 (UTC) To add a note, begin with four tilde signs <nowiki>~~~~</nowiki>; the Wiki will fill in your user name and date.<br />
<br />
[[User:Brecknell|Brecknell]] 13:38, 11 January 2007 (UTC) In Figure 1, retry should be STM a, not STM ().<br />
<br />
[[User:Schmitz|Sylvain]] 13:45, 11 January 2007 (UTC) small points: since you go through explaining that the do-notation is overloaded and works for STM as well as IO (page 8), you might want to tell the same for return on page 11 (return being given with a type a -> IO a on page 5). There is also a double "Here is the code" at the bottom of page 17.<br />
<br />
[[User:Brecknell|Brecknell]] 13:59, 11 January 2007 (UTC) The rewrite of the paragraph at top of page 17 has left behind a fragment that I think just needs to be deleted: "just runs each of the actions in sequence".<br />
<br />
[[User:Brecknell|Brecknell]] 14:15, 11 January 2007 (UTC) Last sentence of page 18: "Here is another way approach that..." Delete either "way" or "approach".<br />
<br />
[[User:ArthurVanLeeuwen|ArthurVanLeeuwen]] 14:27, 11 January 2007 (UTC) minor stuff, really: <br />
* page 2, middle of page: syncrhonized -> synchronized<br />
* page 5, top of page: For example, here are two Haskell functions -> For example, here are the type signatures for two Haskell functions (the functions themselves may be primitives, after all)<br />
* page 5, second paragraph: do the parentheses around hPutStr serve more than to confuse? Especially given their absence for hEchoLine...<br />
* page 5, footnote 3: comma after effects<br />
* page 6: make discarding the return value of forkIO in the second example main more explicit, e.g. with a footnote<br />
* page 7, after Atomicity: This ensured -> This ensures<br />
<br />
[[User:Brecknell|Brecknell]] 14:32, 11 January 2007 (UTC) I like the way you build up to the definition of "choose" in this new revision. I think this helps to convey how STM and actions as first-class values can improve modularity and composability in concurrent applications. So, if you like, you can consider my lsat comment on the previous revision "done", as well.</div>Brecknellhttps://wiki.haskell.org/Talk:SantaClausProblemV2Talk:SantaClausProblemV22007-01-11T14:15:03Z<p>Brecknell: </p>
<hr />
<div>= Beautiful concurrency =<br />
<br />
I am writing a chapter for a book called "Beautiful code", edited by Greg Wilson. The chapter is a tutorial about Software Transactional Memory in Haskell.<br />
<br />
After a lot of useful feedback, I have now completed [http://research.microsoft.com/~simonpj/papers/stm/beautiful.ps Version 2] of the paper. The [http://research.microsoft.com/~simonpj/papers/stm/Santa.hs.gz Haskell code] is also available.<br />
<br />
I would welcome any comments or questions you have on the paper, or constructive suggestions for improving it; the more concrete the better. You can see what people said about version 1 on the version 1 talk page: [[Talk:SantaClausProblem ]].<br />
<br />
The book is aimed at a general audience of programmers, <em>not</em> Haskell geeks, so I have tried to explain everything necessary as I go along. So if you are not a Haskell expert, your input would be particularly valuable to me.<br />
<br />
You can email me directly (simonpj@microsoft.com), or add Wiki talk notes below.<br />
<br />
If you give your real name somewhere in your text (or email it to me), I'll add you to the acknowledgements at the end of the chapter. Notably, I'd like to acknowledge Steven807, Tibbe, Fanf, Garious, Rycee, Brecknell, Mvanier, Gaal, Fernando, Gknauth, EngineerScotty, BoAdler.<br />
<br />
----------<br />
<br />
[[User:Simonpj|Simonpj]] 14:26, 22 December 2006 (UTC) To add a note, begin with four tilde signs <nowiki>~~~~</nowiki>; the Wiki will fill in your user name and date.<br />
<br />
[[User:Brecknell|Brecknell]] 13:38, 11 January 2007 (UTC) In Figure 1, retry should be STM a, not STM ().<br />
<br />
[[User:Schmitz|Sylvain]] 13:45, 11 January 2007 (UTC) small points: since you go through explaining that the do-notation is overloaded and works for STM as well as IO (page 8), you might want to tell the same for return on page 11 (return being given with a type a -> IO a on page 5). There is also a double "Here is the code" at the bottom of page 17.<br />
<br />
[[User:Brecknell|Brecknell]] 13:59, 11 January 2007 (UTC) The rewrite of the paragraph at top of page 17 has left behind a fragment that I think just needs to be deleted: "just runs each of the actions in sequence".<br />
<br />
[[User:Brecknell|Brecknell]] 14:15, 11 January 2007 (UTC) Last sentence of page 18: "Here is another way approach that..." Delete either "way" or "approach".</div>Brecknellhttps://wiki.haskell.org/Talk:SantaClausProblemV2Talk:SantaClausProblemV22007-01-11T13:59:23Z<p>Brecknell: </p>
<hr />
<div>= Beautiful concurrency =<br />
<br />
I am writing a chapter for a book called "Beautiful code", edited by Greg Wilson. The chapter is a tutorial about Software Transactional Memory in Haskell.<br />
<br />
After a lot of useful feedback, I have now completed [http://research.microsoft.com/~simonpj/papers/stm/beautiful.ps Version 2] of the paper. The [http://research.microsoft.com/~simonpj/papers/stm/Santa.hs.gz Haskell code] is also available.<br />
<br />
I would welcome any comments or questions you have on the paper, or constructive suggestions for improving it; the more concrete the better. You can see what people said about version 1 on the version 1 talk page: [[Talk:SantaClausProblem ]].<br />
<br />
The book is aimed at a general audience of programmers, <em>not</em> Haskell geeks, so I have tried to explain everything necessary as I go along. So if you are not a Haskell expert, your input would be particularly valuable to me.<br />
<br />
You can email me directly (simonpj@microsoft.com), or add Wiki talk notes below.<br />
<br />
If you give your real name somewhere in your text (or email it to me), I'll add you to the acknowledgements at the end of the chapter. Notably, I'd like to acknowledge Steven807, Tibbe, Fanf, Garious, Rycee, Brecknell, Mvanier, Gaal, Fernando, Gknauth, EngineerScotty, BoAdler.<br />
<br />
----------<br />
<br />
[[User:Simonpj|Simonpj]] 14:26, 22 December 2006 (UTC) To add a note, begin with four tilde signs <nowiki>~~~~</nowiki>; the Wiki will fill in your user name and date.<br />
<br />
[[User:Brecknell|Brecknell]] 13:38, 11 January 2007 (UTC) In Figure 1, retry should be STM a, not STM ().<br />
<br />
[[User:Schmitz|Sylvain]] 13:45, 11 January 2007 (UTC) small points: since you go through explaining that the do-notation is overloaded and works for STM as well as IO (page 8), you might want to tell the same for return on page 11 (return being given with a type a -> IO a on page 5). There is also a double "Here is the code" at the bottom of page 17.<br />
<br />
[[User:Brecknell|Brecknell]] 13:59, 11 January 2007 (UTC) The rewrite of the paragraph at top of page 17 has left behind a fragment that I think just needs to be deleted: "just runs each of the actions in sequence".</div>Brecknellhttps://wiki.haskell.org/Talk:SantaClausProblemV2Talk:SantaClausProblemV22007-01-11T13:38:10Z<p>Brecknell: </p>
<hr />
<div>= Beautiful concurrency =<br />
<br />
I am writing a chapter for a book called "Beautiful code", edited by Greg Wilson. The chapter is a tutorial about Software Transactional Memory in Haskell.<br />
<br />
After a lot of useful feedback, I have now completed [http://research.microsoft.com/~simonpj/papers/stm/beautiful.ps Version 2] of the paper. The [http://research.microsoft.com/~simonpj/papers/stm/Santa.hs.gz Haskell code] is also available.<br />
<br />
I would welcome any comments or questions you have on the paper, or constructive suggestions for improving it; the more concrete the better. You can see what people said about version 1 on the version 1 talk page: [[Talk:SantaClausProblem ]].<br />
<br />
The book is aimed at a general audience of programmers, <em>not</em> Haskell geeks, so I have tried to explain everything necessary as I go along. So if you are not a Haskell expert, your input would be particularly valuable to me.<br />
<br />
You can email me directly (simonpj@microsoft.com), or add Wiki talk notes below.<br />
<br />
If you give your real name somewhere in your text (or email it to me), I'll add you to the acknowledgements at the end of the chapter. Notably, I'd like to acknowledge Steven807, Tibbe, Fanf, Garious, Rycee, Brecknell, Mvanier, Gaal, Fernando, Gknauth, EngineerScotty, BoAdler.<br />
<br />
----------<br />
<br />
[[User:Simonpj|Simonpj]] 14:26, 22 December 2006 (UTC) To add a note, begin with four tilde signs <nowiki>~~~~</nowiki>; the Wiki will fill in your user name and date.<br />
<br />
[[User:Brecknell|Brecknell]] 13:38, 11 January 2007 (UTC) In Figure 1, retry should be STM a, not STM ().</div>Brecknellhttps://wiki.haskell.org/User:BrecknellUser:Brecknell2006-12-28T12:15:24Z<p>Brecknell: </p>
<hr />
<div>== Matthew Brecknell ==<br />
<br />
<haskell><br />
email = f 563336463087636494483562699911264524058212996 where<br />
f n = let (q,r) = divMod n 137 in chr (fromIntegral r) : case q of { 0 -> []; _ -> f q }<br />
</haskell></div>Brecknellhttps://wiki.haskell.org/Talk:SantaClausProblemTalk:SantaClausProblem2006-12-27T03:41:32Z<p>Brecknell: </p>
<hr />
<div>= Beautiful concurrency =<br />
<br />
I am writing a chapter for a book called "Beautiful code", edited by Greg Wilson. My [http://research.microsoft.com/~simonpj/tmp/beautiful.ps draft chapter] is about Software Transactional Memory in Haskell.<br />
<br />
I would welcome any comments or questions you have on the paper, or constructive suggestions for improving it; the more concrete the better. <br />
<br />
The book is aimed at a general audience of programmers, <em>not</em> Haskell geeks, so I have tried to explain everything necessary as I go along. So if you are not a Haskell expert, your input would be particularly valuable to me.<br />
<br />
You can email me directly (simonpj@microsoft.com), or add Wiki talk notes below.<br />
<br />
----------<br />
<br />
[[User:Simonpj|Simonpj]] 14:26, 22 December 2006 (UTC) To add a note, begin with four tilde signs <nowiki>~~~~</nowiki>; the Wiki will fill in your user name and date.<br />
<br />
----------<br />
<br />
[[User:ArthurVanLeeuwen|ArthurVanLeeuwen]] 16:25, 22 December 2006 (UTC) There's a couple of typos in the paper as it is now. More importantly, the footnote on page 2 has (hGetLine h "hello") where it should state (hPutStr h "hello").<br />
<br />
[[User:NeilMitchell|Neil Mitchell]] 16:28, 22 December 2006 (UTC) Sect 1, Para 2. If we want to write parallel program[s] - missing s.<br />
<br />
<br />
[[User:Steven807|Steven807]] 17:14, 22 December 2006 (UTC) There is no definition or description of '''check'''<br />
<br />
[[User:Tibbe|Tibbe]] 18:33, 22 December 2006 (UTC); The footnote on page 2 now has a incorrectly capitalized T in hPutSTr.<br />
<br />
[[User:Fanf|Fanf]] 18:51, 22 December 2006 (UTC) page 1 para 2 "as well shall see" should be "as we shall see"<br />
<br />
[[User:Fanf|Fanf]] 18:51, 22 December 2006 (UTC) page 3 "a bit like *t in C" should be "a bit like t* in C" since t is a type<br />
<br />
[[User:Garious|Garious]] 18:56, 22 December 2006 (UTC) page 10 "at which point An elf" should be "at which point an elf"<br />
<br />
[[User:Garious|Garious]] 18:58, 22 December 2006 (UTC) page 10 "Here, then is a possible" should be "Here then, is a possible"<br />
<br />
[[User:Garious|Garious]] 19:16, 22 December 2006 (UTC) page 11 "Again, we define Group is declared" whaaa? maybe: "Group is declared as a data type with constructor MkGroup. MkGroup is passed the Group's capacity, and a TVar containing the number of current members and the Group's two Gates."<br />
<br />
[[User:Garious|Garious]] 19:16, 22 December 2006 (UTC) page 11 "Creating a new Group is simply..." Is a process of three somewhat-abstract steps simple enough to say 'simply'? Instead, maybe show the code and let the reader think, "Hey, that's simple!"<br />
<br />
[[User:Rycee|Rycee]] 20:46, 22 December 2006 (UTC) Page 4. You probably want to change "... the action a does ..." to "... the action act does ..."<br />
<br />
[[User:Rycee|Rycee]] 20:46, 22 December 2006 (UTC) Page 8. Typographic nitpick: The space after "i.e." looks wide, perhaps you forgot to write "i.e.\ " to force a regular (non sentence ending) space in LaTeX?<br />
<br />
[[User:MichalPalka|MichalPalka]] 22:32, 22 December 2006 (UTC) You could add a reference to SQL and triggers. They are similar in that it is programming with transations and seeing familiar names will make applied programmers feel more comfortable.<br />
<br />
[[User:DavidHouse|DavidHouse]] 22:55, 22 December 2006 (UTC) Page 3, "That is, return v is a function that, when performed, does no side effects and returns v." Your use of 'that is' implies that you could deduce the fact that it does no side effects from the type signature just given, which isn't true. It's an auxiliary property of 'return'. Maybe just miss out the 'that is'.<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:04, 22 December 2006 (UTC) Bottom of Page 4, "Then 'atomically act' grabs the lock, performs the action 'at',". Missing 'c' out of 'at'.<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:23, 22 December 2006 (UTC) Page 5, "Then 'withdraw' is an STM action that adds amount to the balance in the account." 1) For consistency with the rest of the paper, it should be "Then 'withdraw account ammount'..." 2) withdraw subtracts, not adds, to the amount in the account.<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:40, 22 December 2006 (UTC) Page 9, you probably want to mention that ++ is string concatenation.<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:45, 22 December 2006 (UTC) Page 10, I would expect to see the type signatures for the Gate interface rewritten alongside their definitions.<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:47, 22 December 2006 (UTC) Page 9/10, algebraic datatypes are a little weird for the non-initiated, especially with constructors that don't appear to do anything ("Where do you define MkGate?" etc.). You might want to liken them to C's structs, and explain the constructors as tags?<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:57, 22 December 2006 (UTC) Page 13, I don't think you sufficiently explain 'sequence'. You may wish to add a sentence along the lines of "'sequence' is a function that takes a list of IO actions and returns the action that, when executed, runs each of the actions you passed it in turn."<br />
<br />
[[User:Dalejordan|Dalejordan]] 02:15, 23 December 2006 (UTC) For the sake of us newbs you might mention in Section 2.1 how all these actions ever get performed. Also, in your description of nTimes I think it would be clearer to say it creates a composite action that performs its argument action n times, rather than say it performs it (directly) n times, even though the value of n is not yet known. Another example of the "beauty" of first class actions (and recursion).<br />
<br />
[[User:Brecknell|Brecknell]] 03:29, 23 December 2006 (UTC) Page 7: withdraw should subtract, not add amount to the balance (sadly). Also, since this withdraw has different semantics to the version on p5, you may want to consider giving it a different name.<br />
<br />
[[User:Brecknell|Brecknell]] 03:29, 23 December 2006 (UTC) Page 8, towards the end of section 2.4: Two instances of "withdraw" should be "withdraw2", one in the function definition and one in the comment.<br />
<br />
[[User:Brecknell|Brecknell]] 05:04, 23 December 2006 (UTC) In the problem definition, "Santa repeatedly sleeps until wakened...", but with the definition of "forever" given in the text, and without some sort of asynchronous signalling, it looks to me like Santa will sleep for at least as long as his random number generator tells him to. Perhaps move the sleep out of forever and into elf and reindeer, then Santa will just sleep in awaitGroup.<br />
<br />
[[User:Mvanier|Mvanier]] 19:21, 23 December 2006 (UTC) In section 3.3, "sequence" might as well just be "sequence_". It's confusing to return a list of unit values and not do anything with them. In section 5, I think that the problem with composing lock-based concurrent functions could be explained better; the statement "instead we must expose the locking protocol" could be expanded to show why this is the case.<br />
<br />
[[User:ChrisKuklewicz|ChrisKuklewicz]] 22:17, 24 December 2006 (UTC) In learning Haskell STM back in October of 1995 I had written a solution to the same Santa problem. The main suggestion I have is that the elf and reindeer are given two actions (use Gate inGate) and (useGate outGate) and are required to properly bracket their actual action between these two. If the (joinGroup group) call returned a single scoping combinator (bracket_ (useGate inGate) (useGate outGate)) then the concurrency model for the elf and reindeer would be even to get correct (and beautiful?). Furthermore they could be passed (joinGroup group) instead of (group). This prevents the elf and reindeer from calling any other group functions.<br />
<br />
[[User:Conal|Conal]] 16:39, 25 December 2006 (UTC) Page 11, first full paragraph, "then waits to the TVar to be decremented to zero." Replace "waits to" with "waits for".<br />
<br />
[[User:Brecknell|Brecknell]] 03:41, 27 December 2006 (UTC) This was my first exposure to STM, and I found it clear and easy enough to follow. However, I think it is mainly the discussion of bank accounts that conveys the "beauty" of STM, since that's where the important concepts are demonstrated: composability of transactions, implicit locking and deadlock avoidance, etc. In the Santa Claus problem, those concepts are somewhat obscured. I think the Santa Claus problem is still useful for demonstrating how STM can handle a tricky concurrency scenario with relative ease, but it didn't give me the sense of clarity that the discussion of bank accounts did. Maybe the Santa Claus solution needs more focus on the abstractions possible in STM, how they can help modularise concurrent programs, and why STM is better for solving concurrency problems than the concurrency primitives available elsewhere.</div>Brecknellhttps://wiki.haskell.org/Talk:SantaClausProblemTalk:SantaClausProblem2006-12-23T05:04:50Z<p>Brecknell: </p>
<hr />
<div>= Beautiful concurrency =<br />
<br />
I am writing a chapter for a book called "Beautiful code", edited by Greg Wilson. My [http://research.microsoft.com/~simonpj/tmp/beautiful.ps draft chapter] is about Software Transactional Memory in Haskell.<br />
<br />
I would welcome any comments or questions you have on the paper, or constructive suggestions for improving it; the more concrete the better. <br />
<br />
The book is aimed at a general audience of programmers, <em>not</em> Haskell geeks, so I have tried to explain everything necessary as I go along. So if you are not a Haskell expert, your input would be particularly valuable to me.<br />
<br />
You can email me directly (simonpj@microsoft.com), or add Wiki talk notes below.<br />
<br />
----------<br />
<br />
[[User:Simonpj|Simonpj]] 14:26, 22 December 2006 (UTC) To add a note, begin with four tilde signs <nowiki>~~~~</nowiki>; the Wiki will fill in your user name and date.<br />
<br />
----------<br />
<br />
[[User:ArthurVanLeeuwen|ArthurVanLeeuwen]] 16:25, 22 December 2006 (UTC) There's a couple of typos in the paper as it is now. More importantly, the footnote on page 2 has (hGetLine h "hello") where it should state (hPutStr h "hello").<br />
<br />
[[User:NeilMitchell|Neil Mitchell]] 16:28, 22 December 2006 (UTC) Sect 1, Para 2. If we want to write parallel program[s] - missing s.<br />
<br />
<br />
[[User:Steven807|Steven807]] 17:14, 22 December 2006 (UTC) There is no definition or description of '''check'''<br />
<br />
[[User:Tibbe|Tibbe]] 18:33, 22 December 2006 (UTC); The footnote on page 2 now has a incorrectly capitalized T in hPutSTr.<br />
<br />
[[User:Fanf|Fanf]] 18:51, 22 December 2006 (UTC) page 1 para 2 "as well shall see" should be "as we shall see"<br />
<br />
[[User:Fanf|Fanf]] 18:51, 22 December 2006 (UTC) page 3 "a bit like *t in C" should be "a bit like t* in C" since t is a type<br />
<br />
[[User:Garious|Garious]] 18:56, 22 December 2006 (UTC) page 10 "at which point An elf" should be "at which point an elf"<br />
<br />
[[User:Garious|Garious]] 18:58, 22 December 2006 (UTC) page 10 "Here, then is a possible" should be "Here then, is a possible"<br />
<br />
[[User:Garious|Garious]] 19:16, 22 December 2006 (UTC) page 11 "Again, we define Group is declared" whaaa? maybe: "Group is declared as a data type with constructor MkGroup. MkGroup is passed the Group's capacity, and a TVar containing the number of current members and the Group's two Gates."<br />
<br />
[[User:Garious|Garious]] 19:16, 22 December 2006 (UTC) page 11 "Creating a new Group is simply..." Is a process of three somewhat-abstract steps simple enough to say 'simply'? Instead, maybe show the code and let the reader think, "Hey, that's simple!"<br />
<br />
[[User:Rycee|Rycee]] 20:46, 22 December 2006 (UTC) Page 4. You probably want to change "... the action a does ..." to "... the action act does ..."<br />
<br />
[[User:Rycee|Rycee]] 20:46, 22 December 2006 (UTC) Page 8. Typographic nitpick: The space after "i.e." looks wide, perhaps you forgot to write "i.e.\ " to force a regular (non sentence ending) space in LaTeX?<br />
<br />
[[User:MichalPalka|MichalPalka]] 22:32, 22 December 2006 (UTC) You could add a reference to SQL and triggers. They are similar in that it is programming with transations and seeing familiar names will make applied programmers feel more comfortable.<br />
<br />
[[User:DavidHouse|DavidHouse]] 22:55, 22 December 2006 (UTC) Page 3, "That is, return v is a function that, when performed, does no side effects and returns v." Your use of 'that is' implies that you could deduce the fact that it does no side effects from the type signature just given, which isn't true. It's an auxiliary property of 'return'. Maybe just miss out the 'that is'.<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:04, 22 December 2006 (UTC) Bottom of Page 4, "Then 'atomically act' grabs the lock, performs the action 'at',". Missing 'c' out of 'at'.<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:23, 22 December 2006 (UTC) Page 5, "Then 'withdraw' is an STM action that adds amount to the balance in the account." 1) For consistency with the rest of the paper, it should be "Then 'withdraw account ammount'..." 2) withdraw subtracts, not adds, to the amount in the account.<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:40, 22 December 2006 (UTC) Page 9, you probably want to mention that ++ is string concatenation.<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:45, 22 December 2006 (UTC) Page 10, I would expect to see the type signatures for the Gate interface rewritten alongside their definitions.<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:47, 22 December 2006 (UTC) Page 9/10, algebraic datatypes are a little weird for the non-initiated, especially with constructors that don't appear to do anything ("Where do you define MkGate?" etc.). You might want to liken them to C's structs, and explain the constructors as tags?<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:57, 22 December 2006 (UTC) Page 13, I don't think you sufficiently explain 'sequence'. You may wish to add a sentence along the lines of "'sequence' is a function that takes a list of IO actions and returns the action that, when executed, runs each of the actions you passed it in turn."<br />
<br />
[[User:Dalejordan|Dalejordan]] 02:15, 23 December 2006 (UTC) For the sake of us newbs you might mention in Section 2.1 how all these actions ever get performed. Also, in your description of nTimes I think it would be clearer to say it creates a composite action that performs its argument action n times, rather than say it performs it (directly) n times, even though the value of n is not yet known. Another example of the "beauty" of first class actions (and recursion).<br />
<br />
[[User:Brecknell|Brecknell]] 03:29, 23 December 2006 (UTC) Page 7: withdraw should subtract, not add amount to the balance (sadly). Also, since this withdraw has different semantics to the version on p5, you may want to consider giving it a different name.<br />
<br />
[[User:Brecknell|Brecknell]] 03:29, 23 December 2006 (UTC) Page 8, towards the end of section 2.4: Two instances of "withdraw" should be "withdraw2", one in the function definition and one in the comment.<br />
<br />
[[User:Brecknell|Brecknell]] 05:04, 23 December 2006 (UTC) In the problem definition, "Santa repeatedly sleeps until wakened...", but with the definition of "forever" given in the text, and without some sort of asynchronous signalling, it looks to me like Santa will sleep for at least as long as his random number generator tells him to. Perhaps move the sleep out of forever and into elf and reindeer, then Santa will just sleep in awaitGroup.</div>Brecknellhttps://wiki.haskell.org/Talk:SantaClausProblemTalk:SantaClausProblem2006-12-23T03:29:00Z<p>Brecknell: </p>
<hr />
<div>= Beautiful concurrency =<br />
<br />
I am writing a chapter for a book called "Beautiful code", edited by Greg Wilson. My [http://research.microsoft.com/~simonpj/tmp/beautiful.ps draft chapter] is about Software Transactional Memory in Haskell.<br />
<br />
I would welcome any comments or questions you have on the paper, or constructive suggestions for improving it; the more concrete the better. <br />
<br />
The book is aimed at a general audience of programmers, <em>not</em> Haskell geeks, so I have tried to explain everything necessary as I go along. So if you are not a Haskell expert, your input would be particularly valuable to me.<br />
<br />
You can email me directly (simonpj@microsoft.com), or add Wiki talk notes below.<br />
<br />
----------<br />
<br />
[[User:Simonpj|Simonpj]] 14:26, 22 December 2006 (UTC) To add a note, begin with four tilde signs <nowiki>~~~~</nowiki>; the Wiki will fill in your user name and date.<br />
<br />
----------<br />
<br />
[[User:ArthurVanLeeuwen|ArthurVanLeeuwen]] 16:25, 22 December 2006 (UTC) There's a couple of typos in the paper as it is now. More importantly, the footnote on page 2 has (hGetLine h "hello") where it should state (hPutStr h "hello").<br />
<br />
[[User:NeilMitchell|Neil Mitchell]] 16:28, 22 December 2006 (UTC) Sect 1, Para 2. If we want to write parallel program[s] - missing s.<br />
<br />
<br />
[[User:Steven807|Steven807]] 17:14, 22 December 2006 (UTC) There is no definition or description of '''check'''<br />
<br />
[[User:Tibbe|Tibbe]] 18:33, 22 December 2006 (UTC); The footnote on page 2 now has a incorrectly capitalized T in hPutSTr.<br />
<br />
[[User:Fanf|Fanf]] 18:51, 22 December 2006 (UTC) page 1 para 2 "as well shall see" should be "as we shall see"<br />
<br />
[[User:Fanf|Fanf]] 18:51, 22 December 2006 (UTC) page 3 "a bit like *t in C" should be "a bit like t* in C" since t is a type<br />
<br />
[[User:Garious|Garious]] 18:56, 22 December 2006 (UTC) page 10 "at which point An elf" should be "at which point an elf"<br />
<br />
[[User:Garious|Garious]] 18:58, 22 December 2006 (UTC) page 10 "Here, then is a possible" should be "Here then, is a possible"<br />
<br />
[[User:Garious|Garious]] 19:16, 22 December 2006 (UTC) page 11 "Again, we define Group is declared" whaaa? maybe: "Group is declared as a data type with constructor MkGroup. MkGroup is passed the Group's capacity, and a TVar containing the number of current members and the Group's two Gates."<br />
<br />
[[User:Garious|Garious]] 19:16, 22 December 2006 (UTC) page 11 "Creating a new Group is simply..." Is a process of three somewhat-abstract steps simple enough to say 'simply'? Instead, maybe show the code and let the reader think, "Hey, that's simple!"<br />
<br />
[[User:Rycee|Rycee]] 20:46, 22 December 2006 (UTC) Page 4. You probably want to change "... the action a does ..." to "... the action act does ..."<br />
<br />
[[User:Rycee|Rycee]] 20:46, 22 December 2006 (UTC) Page 8. Typographic nitpick: The space after "i.e." looks wide, perhaps you forgot to write "i.e.\ " to force a regular (non sentence ending) space in LaTeX?<br />
<br />
[[User:MichalPalka|MichalPalka]] 22:32, 22 December 2006 (UTC) You could add a reference to SQL and triggers. They are similar in that it is programming with transations and seeing familiar names will make applied programmers feel more comfortable.<br />
<br />
[[User:DavidHouse|DavidHouse]] 22:55, 22 December 2006 (UTC) Page 3, "That is, return v is a function that, when performed, does no side effects and returns v." Your use of 'that is' implies that you could deduce the fact that it does no side effects from the type signature just given, which isn't true. It's an auxiliary property of 'return'. Maybe just miss out the 'that is'.<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:04, 22 December 2006 (UTC) Bottom of Page 4, "Then 'atomically act' grabs the lock, performs the action 'at',". Missing 'c' out of 'at'.<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:23, 22 December 2006 (UTC) Page 5, "Then 'withdraw' is an STM action that adds amount to the balance in the account." 1) For consistency with the rest of the paper, it should be "Then 'withdraw account ammount'..." 2) withdraw subtracts, not adds, to the amount in the account.<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:40, 22 December 2006 (UTC) Page 9, you probably want to mention that ++ is string concatenation.<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:45, 22 December 2006 (UTC) Page 10, I would expect to see the type signatures for the Gate interface rewritten alongside their definitions.<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:47, 22 December 2006 (UTC) Page 9/10, algebraic datatypes are a little weird for the non-initiated, especially with constructors that don't appear to do anything ("Where do you define MkGate?" etc.). You might want to liken them to C's structs, and explain the constructors as tags?<br />
<br />
[[User:DavidHouse|DavidHouse]] 23:57, 22 December 2006 (UTC) Page 13, I don't think you sufficiently explain 'sequence'. You may wish to add a sentence along the lines of "'sequence' is a function that takes a list of IO actions and returns the action that, when executed, runs each of the actions you passed it in turn."<br />
<br />
[[User:Dalejordan|Dalejordan]] 02:15, 23 December 2006 (UTC) For the sake of us newbs you might mention in Section 2.1 how all these actions ever get performed. Also, in your description of nTimes I think it would be clearer to say it creates a composite action that performs its argument action n times, rather than say it performs it (directly) n times, even though the value of n is not yet known. Another example of the "beauty" of first class actions (and recursion).<br />
<br />
[[User:Brecknell|Brecknell]] 03:29, 23 December 2006 (UTC) Page 7: withdraw should subtract, not add amount to the balance (sadly). Also, since this withdraw has different semantics to the version on p5, you may want to consider giving it a different name.<br />
<br />
[[User:Brecknell|Brecknell]] 03:29, 23 December 2006 (UTC) Page 8, towards the end of section 2.4: Two instances of "withdraw" should be "withdraw2", one in the function definition and one in the comment.</div>Brecknellhttps://wiki.haskell.org/Generalised_algebraic_datatypeGeneralised algebraic datatype2006-11-09T23:37:11Z<p>Brecknell: fix broken link</p>
<hr />
<div>== Papers ==<br />
<br />
See also [[Research papers/Type systems#Generalised Algebraic Data Types|research papers on type systems]].<br />
<br />
* A short descriptions on generalised algebraic datatypes here [http://haskell.org/ghc/docs/latest/html/users_guide/gadt.html as GHC language features].<br />
* Another description with links on [http://hackage.haskell.org/trac/haskell-prime/wiki/GADTs Haskell' wiki].<br />
* [http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2003-1901 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/Users/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.comp.nus.edu.sg/~sulzmann/manuscript/simple-translate-gadts.ps Translating Generalized Algebraic Data Types to System F] written by [http://www.comp.nus.edu.sg/~sulzmann/ Martin Sulzmann] and Meng Wang. [http://www.comp.nus.edu.sg/~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 slides [http://darcs.net/fosdem_talk/talk.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 />
[[Category:Language]]</div>Brecknellhttps://wiki.haskell.org/Research_papers/Type_systemsResearch papers/Type systems2006-11-09T21:16:32Z<p>Brecknell: fix some broken links</p>
<hr />
<div>__TOC__<br />
<br />
==Haskell semantics==<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/static-semantics.dvi.gz A static semantics for Haskell]<br />
:SL Peyton Jones and PL Wadler, (draft), Department of Computing Science, University of Glasgow, 1992. (Cited by 20)<br />
<br />
;[http://haskell.org/onlinereport/dynamic-semantics.dvi.gz A Dynamic Semantics for Haskell] <br />
:Kevin Hammond and Cordelia Hall, (draft), University of Glasgow, 1992, 23 pages.<br />
<br />
;[http://www.cse.ogi.edu/~mpj/pubs/thih.html Typing Haskell in Haskell] <br />
:Mark P. Jones, In Proceedings of the 1999 Haskell Workshop, Paris, France, October 1999. Published in Technical Report UU-CS-1999-28, Department of Computer Science, University of Utrecht. (Cited by 66)<br />
<br />
;[http://www.pms.informatik.uni-muenchen.de/mitarbeiter/panne/haskell_libs/hsparser.html HParser]<br />
:A parser for Haskell written purely in Haskell (using the Happy parser generator).<br />
<br />
;[http://www.cse.ogi.edu/~hallgren/Talks/LHiH/ A Lexer for Haskell in Haskell]<br />
:Thomas Hallgren, PacSoft Oregon Graduate Institute, 14 January, 2002<br />
<br />
;[http://citeseer.ist.psu.edu/launchbury93natural.html A Natural Semantics for Lazy Evaluation]<br />
:John Launchbury, Conference Record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Charleston, South Carolina, 144--154, 1993.<br />
<br />
;[http://www.cs.nott.ac.uk/~gmh/papers/11.ps A Space Semantics for Core Haskell]<br />
:Adam Bakewell. Proc. 2000 Haskell Workshop. September 2001.<br />
<br />
==Pure type systems==<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/henk.ps.gz Henk: a typed intermediate language]<br />
:SL Peyton Jones and E Meijer, Proceedings of the Types in Compilation Workshop, Amsterdam, June 1997.<br />
<br />
;[http://www.cs.uu.nl/~johanj/MSc/jwroorda/ Pure Type Systems for Functional Programming]<br />
:Jan-Willem Roorda, Masters Thesis, University of Utrecht, INF/SCR-00-13, available online, 2000<br />
<br />
==Dependent Types==<br />
<br />
;[http://www.cs.nott.ac.uk/~txa/publ/ydtm.pdf Why Dependent Types Matter]<br />
:Thorsten Altenkirch and Conor McBride and James McKinna, Manuscript, available online, April, 2005. (Cited by 7)<br />
<br />
==Unboxed values==<br />
<br />
;[http://www.soi.city.ac.uk/~ross/papers/pointed.html Parametricity and Unboxing with Unpointed Types]<br />
:John Launchbury and Ross Paterson, European Symposium on Programming, LNCS, vol. 1058, pp. 204-218, Springer, Linkping, Sweden, 1996.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/unboxed-values.ps.Z Unboxed values as first class citizens]<br />
:SL Peyton Jones and J Launchbury, Functional Programming Languages and Computer Architecture (FPCA'91), Boston, LNCS 523, Springer Verlag, Sept 1991, pp636-666. (Cited by 105)<br />
<br />
==Modules==<br />
<br />
;[http://www.cse.ogi.edu/~diatchki/papers/modules98.pdf A Formal Specification of the Haskell 98 Module System]<br />
:Iavor S. Diatchki, Mark P. Jones, and Thomas Hallgren. Proceedings of the 2002 ACM SIGPLAN workshop on Haskell. Pittsburgh, Pennsylvania. 17 - 28 2002 ISBN 1-58113-605-6 (Cited by 12)<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/first-class-modules/index.htm First class modules for Haskell]<br />
:Mark Shields and Simon Peyton Jones; FOOL'02.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/Nicklisch-modules.ps.gz An exploration of modular programs]<br />
:Electronic proceedings of the 1996 Glasgow Functional Programming Workshop, J Nicklisch and SL Peyton Jones, Ullapool, July 1996.<br />
<br />
==Exceptions==<br />
<br />
;[http://www.haskell.org/~simonmar/papers/ext-exceptions.pdf An Extensible Dynamically-Typed Hierarchy of Exceptions]<br />
:Simon Marlow. Haskell '06: Proceedings of the 2006 ACM SIGPLAN workshop on Haskell, Portland, Oregon, ACM Press, September 2006<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/imprecise-exn-sem.htm Imprecise Exceptions, Co-Inductively]<br />
:Andy Moran, Soeren Lassen, and Simon Peyton Jones. HOOTS'99.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/imprecise-exn.htm A semantics for imprecise exceptions]<br />
:Simon Peyton Jones, Alastair Reid, Tony Hoare, Simon Marlow, Fergus Henderson. Proc Programming Language Design and Implementation (PLDI'99), Atlanta.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/asynch-exns.htm Asynchronous exceptions in Haskell]<br />
:Simon Marlow, Simon Peyton Jones, Andy Moran and John Reppy, PLDI'01.<br />
<br />
;[http://www.reid-consulting-uk.ltd.uk/alastair/publications/except6.ps.gz Handling Exceptions in Haskell]<br />
:A. Reid, Research Report YALEU/DCS/RR-1175, Yale University, August, 1998<br />
<br />
==Records==<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/records.htm Lightweight Extensible Records for Haskell]<br />
:Mark Jones and Simon Peyton Jones, Haskell Workshop 1999.<br />
<br />
;[http://www.cs.uu.nl/~daan/download/papers/scopedlabels.pdf Extensible records with scoped labels]<br />
:Daan Leijen. The 2005 Symposium on Trends in Functional Programming (TFP'05), Tallin, Estonia, September 2005.<br />
<br />
;[http://www.cs.uu.nl/~daan/download/papers/fclabels.pdf First-class labels for extensible rows]<br />
:Daan Leijen. Technical Report UU-CS-2004-51, Departement of Computer Science, Universiteit Utrecht, 2004.<br />
<br />
;[http://www.reid-consulting-uk.ltd.uk/alastair/publications/h-wkshop95a/index.html Haskell Records]<br />
:J. Peterson, A. Reid, Proceedings of the Haskell Workshop, La Jolla, June 1995. <br />
<br />
;[http://www.cse.ogi.edu/~mpj/pubs/96-3.ps.gz A Polymorphic Type System for Extensible Records and Variants]<br />
:Benedict R. Gaster and Mark P. Jones. Department of Computer Science, University of Nottingham. Technical report NOTTCS-TR-96-3. November 1996.<br />
<br />
==Meta programming==<br />
<br />
;[http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/dyntyping.ps.gz&pub=ACM Dynamic typing as staged type inference]<br />
:MB Shields, T Sheard, and SL Peyton Jones, POPL98.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/meta-haskell/index.htm Template meta-programming for Haskell]<br />
:Tim Sheard and Simon Peyton Jones, Proceedings of the Haskell Workshop, Pittsburgh, 2002<br />
<br />
;[http://www.cse.unsw.edu.au/~chak/papers/SCK04.html Optimising Embedded DSLs using Template Haskell]<br />
:Sean Seefried, Manuel M. T. Chakravarty, and Gabriele Keller. In Gabor Karsai and Eelco Visser, editors, Third International Conference on Generative Programming and Component Engineering (GPCE'04), LNCS 3286, Springer-Verlag, pages 186-205, 2004. [An earlier draft was presented at the IFL 2003 - 15th International Workshop on the Implementation of Functional Languages, 2003.<br />
<br />
;[http://www.haskell.org/th/papers/Unrolling_and_Simplifying_Expressions_with_Template_Haskell.ps Unrolling and Simplifying Expressions with Template Haskell]<br />
:Ian Lynagh, May 2003.<br />
<br />
;[http://www.haskell.org/th/papers/hlpp.ps Automatic skeletons in Template Haskell]<br />
:Kevin Hammond, Jost Berthold and Rita Loogen, June 2003. Proceedings of 2003 Workshop on High Level Parallel Programming, Paris, France<br />
<br />
;[http://www.haskell.org/th/papers/Typing_Template_Haskell__Soft_Types.ps Typing Template Haskell: Soft Types]<br />
:Ian Lynagh, August 2004.<br />
<br />
==Dynamic typing==<br />
<br />
;[http://www.cs.uu.nl/groups/ST/stbib/swierstra-by-year/BaSw02.bib Typing dynamic typing]<br />
:A. I. Baars and S. D. Swierstra. In S. Peyton Jones, editor, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, pages 157--166. ACM Press, 2002<br />
<br />
==Parametricity==<br />
<br />
;[http://homepages.inf.ed.ac.uk/wadler/papers/free/free.ps.gz Theorems for free!]<br />
:Philip Wadler. 4'th International Conference on Functional Programming and Computer Architecture, London, September 1989.<br />
<br />
;[http://www.soi.city.ac.uk/~ross/papers/pointed.html Parametricity and Unboxing with Unpointed Types]<br />
:John Launchbury and Ross Paterson, European Symposium on Programming, LNCS, vol. 1058, pp. 204-218, Springer, Linkping, Sweden, 1996.<br />
<br />
;[http://wwwtcs.inf.tu-dresden.de/~voigt/seqFinal.pdf The Impact of seq on Free Theorems-Based Program Transformations]<br />
:Patricia Johann and Janis Voigtländer, Fundamenta Informaticae, vol. 69(1-2), pp. 63-102, 2006.<br />
<br />
==Type classes==<br />
<br />
;[http://homepages.inf.ed.ac.uk/wadler/papers/class/class.ps.gz How to make ad-hoc polymorphism less ad hoc]<br />
:Philip Wadler and Stephen Blott. 16'th Symposium on Principles of Programming Languages, ACM Press, Austin, Texas, January 1989.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/classhask.ps.gz Type classes in Haskell, CV Hall, K Hammond, SL Peyton Jones, and PL Wadler]<br />
:European Symposium On Programming, LNCS 788, Springer Verlag, pp. 241-256, April 1994. (Cited by 131)<br />
<br />
;[http://www.cse.ogi.edu/~mpj/pubs/pldi93.html Implementing Type Classes]<br />
:John Peterson and Mark P. Jones, In Proceedings of ACM SIGPLAN Symposium on Programming Language Design and Implementation, ACM SIGPLAN, June 1993. (Cited by 40)<br />
<br />
;[http://www.cs.chalmers.se/pub/cs-reports/papers/overload-fpca-93.ps.Z Implementing Haskell overloading]<br />
:Lennart Augustsson, 1993. FPCA. 65-73<br />
<br />
;[http://www.cse.ogi.edu/~mpj/pubs/springschool.html Functional Programming with Overloading and Higher-Order Polymorphism]<br />
:Mark P. Jones, First International Spring School on Advanced Functional Programming Techniques, Baastad, Sweden, Springer-Verlag Lecture Notes in Computer Science 925, May 1995.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/type-class-design-space Type classes: exploring the design space]<br />
:Simon Peyton Jones, Mark Jones, Erik Meijer, Haskell Workshop 1997.<br />
<br />
;[http://www.cse.ogi.edu/~mpj/pubs/fpca93.html A system of constructor classes: overloading and implicit higher-order polymorphism]<br />
:Mark P. Jones, In FPCA '93: Conference on Functional Programming Languages and Computer Architecture, Copenhagen, Denmark, June 1993.<br />
<br />
;[http://homepages.inf.ed.ac.uk/wadler/papers/overload2/overload2.ps.gz A second look at overloading]<br />
:Martin Odersky, Philip Wadler, Martin Wehr. 7'th International Conference on Functional Programming and Computer Architecture, ACM Press, San Diego, California, June 1995.<br />
<br />
;[http://citeseer.ist.psu.edu/laufer94combining.html Combining Type Classes and Existential Types]<br />
:Konstantin Laufer, Proceedings of the Latin American Informatic Conference (PANEL), 1994<br />
<br />
;[http://citeseer.ifi.unizh.ch/laeufer95type.html Type Classes with Existential Types]<br />
:Konstantin Laufer, Journal of Functional Programming, 1996, May<br />
<br />
;[http://www.cse.unsw.edu.au/~chak/papers/DHCK06.html Modular Type Classes]<br />
:Derek Dreyer, Robert Harper, Manuel M.T. Chakravarty and Gabriele Keller, 2006<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/hw2001/4.pdf Named instances for Haskell type classes]<br />
:W Kahl, J Scheffczyk - Proc. Haskell Workshop, 2001 (Cited by 12)<br />
<br />
===Deriving type classes===<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/derive.htm Derivable Type classes] <br />
:Ralf Hinze and Simon Peyton Jones, Haskell Workshop 2000.<br />
<br />
;[http://www.cis.upenn.edu/~sweirich/RepLib/ RepLib: A Library for Derivable Type Classes]<br />
:Stephanie Weirich 2006<br />
<br />
===Applications of type classes===<br />
<br />
;[http://okmij.org/ftp/Haskell/number-parameterized-types.html Number-parameterized types]<br />
:Oleg Kiselyov, The Monad.Reader. IssueFive. Oct 2nd, 2005<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, Jeremy Gibbons. Proceedings of the 2005 ACM SIGPLAN workshop on Haskell. Tallinn, Estonia. 98 - 109, 2005 ISBN:1-59593-071-X<br />
<br />
;[http://okmij.org/ftp/Haskell/types.html#Prepose Functional pearl: implicit configurations--or, type classes reflect the values of types]<br />
:Oleg Kiselyov, Chung-chieh Shan, Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, Snowbird, Utah, USA, 2004 ISBN 1-58113-850-4<br />
<br />
;[http://www.comp.nus.edu.sg/~sulzmann/publications/extract-typeclassproofs.pdf Extracting Programs from Type Class Proofs]<br />
:Martin Sulzmann, 2006<br />
<br />
;[http://www.comp.nus.edu.sg/~sulzmann/manuscript/coind-type-class-proofs.ps Co-induction and Type Improvement in Type Class Proofs]<br />
:Martin Sulzmann, Jeremy Wazny and Peter J. Stuckey. 2005<br />
<br />
;[http://www.cs.nott.ac.uk/~ctm/faking.ps.gz Faking It (Simulating Dependent Types in Haskell)]<br />
:Conor McBride, Journal of Functional Programming, 12(4&5):375-392, July 2002<br />
<br />
==Undecidable instances==<br />
<br />
;[http://www.haskell.org/ghc/docs/6.4.2/html/users_guide/type-extensions.html#undecidable-instances Undecidable instances]<br />
:GHC User's Guide.<br />
<br />
==Multi-parameter type classes==<br />
<br />
;[http://www.comp.nus.edu.sg/~sulzmann/manuscript/mptc-inf-old.pdf Type Inference for Multi-Parameter Type Classes]<br />
:Martin Sulzmann and Peter J. Stuckey. 2005<br />
<br />
;[http://ostrich.lcs.mit.edu/cgi-bin/pickbib?jfp::DugganO2002 Type-checking multi-parameter type classes]<br />
:Dominic Duggan and John Ophel, Journal of Functional Programming, 12(2):133-158, March 2002<br />
<br />
==Functional dependencies==<br />
<br />
;[http://www.cse.ogi.edu/~mpj/pubs/fundeps.html Type Classes with Functional Dependencies]<br />
:Mark P. Jones, In Proceedings of the 9th European Symposium on Programming, ESOP 2000, Berlin, Germany, March 2000, Springer-Verlag LNCS 1782.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/fd-chr/index.htm Sound and Decidable Type Inference for Functional Dependencies]<br />
:Gregory J. Duck, Simon Peyton Jones, Peter J. Stuckey, and Martin Sulzmann, European Symposium on Programming 2004 (ESOP'04).<br />
<br />
;[http://www.comp.nus.edu.sg/~sulzmann/publications/jfp-fds-revised.pdf Understanding Functional Dependencies via Constraint Handling Rules]<br />
:Martin Sulzmann, Gregory J. Duck, Simon Peyton-Jones and Peter J. Stuckey.j To appear in Journal of Functional Programming. 2006<br />
<br />
;[http://www.comp.nus.edu.sg/~sulzmann/manuscript/afds.ps Associated Functional Dependencies]<br />
:Martin Sulzmann and Edmund Soon Lee Lam. 2005<br />
<br />
==Generalised Algebraic Data Types==<br />
<br />
;[http://research.microsoft.com/~simonpj/papers/gadt/index.htm Simple unification-based type inference for GADTs]<br />
:Simon Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, and Geoffrey Washburn. Submitted to PLDI 2005<br />
<br />
;[http://www.cis.upenn.edu/~geoffw/research/papers/MS-CIS-05-26.pdf Wobbly types: type inference for generalised algebraic data types]<br />
:S Peyton Jones, G. Washburn, and S. Weirich. 2004.<br />
<br />
;[http://www.comp.nus.edu.sg/~sulzmann/manuscript/simple-translate-gadts.ps Translating Generalized Algebraic Data Types to System F]<br />
:Martin Sulzmann and Meng Wang. 2005<br />
<br />
;[http://cristal.inria.fr/~fpottier/publis/pottier-regis-gianas-05.pdf Stratified type inference for generalized algebraic data types]<br />
:François Pottier and Yann Régis-Gianas, 2006<br />
<br />
==Associated types==<br />
<br />
;[http://www.haskell.org/~simonmar/papers/assoc.pdf Associated types with class]<br />
:Manuel M. T. Chakravarty, Gabriele Keller, Simon Peyton Jones, Simon Marlow) POPL '05: Proceedings of the 32nd ACM SIGPLAN-SIGACT sysposium on Principles of programming languages, pages 1--13, Long Beach, California, USA, ACM Press, 2005<br />
<br />
;[http://www.cse.unsw.edu.au/~chak/papers/CKP05.html Associated Type Synonyms]<br />
:Manuel M. T. Chakravarty, Gabriele Keller, and Simon Peyton Jones. In Proceedings of The Tenth ACM SIGPLAN International Conference on Functional Programming, ACM Press, pages 241-253, 2005.<br />
<br />
;[http://www.informatik.uni-freiburg.de/~wehr/diplom ML Modules and Haskell Type Classes: A Constructive Comparison]<br />
:Stefan Wehr Diplomarbeit. Albert-Ludwigs-Universitt Freiburg, Fakultt fr Angewandte Wissenschaften, Institut fr Informatik, November 2005. <br />
<br />
;[http://www.cse.unsw.edu.au/~chak/papers/SCP06.html System F with Type Equality Coercions]<br />
:Martin Sulzmann, Manuel M. T. Chakravarty, and Simon Peyton Jones.<br />
<br />
==Arbitrary-rank polymorphism==<br />
<br />
;[http://www.ubka.uni-karlsruhe.de/vvv/1996/informatik/81/81.pdf.gz Putting type annotations to work]<br />
:Martin Odersky and Konstantin Läufer. Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages. St. Petersburg Beach, Florida, United States. 54 - 67 1996 ISBN 0-89791-769-3<br />
<br />
;[http://journals.cambridge.org/production/action/cjoGetFulltext%3Ffulltextid%3D445910 Practical type inference for arbitrary-rank types]<br />
:SP Jones, M Shields - Submitted to the Journal of Functional Programming, 2005<br />
<br />
==Phantom types==<br />
<br />
;[http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2003-1901 First-class phantom types]<br />
:James Cheney and Ralf Hinze. Technical Report TR2003-1901, Cornell University, 2003.<br />
<br />
==Implicit parameters==<br />
<br />
;[http://www.cse.ogi.edu/~mbs/pub/implicit_parameters/implicit.ps Implicit Parameters: Dynamic Scoping with Static Types]<br />
:Jeffrey Lewis, Mark Shields, Erik Meijer and John Launchbury. POPL'00. 2000.<br />
<br />
;[http://www.cs.chalmers.se/~rjmh/Globals.ps Global variables in Haskell]<br />
:John Hughes. J. Funct. Program. 14(5): 489-502 (2004) <br />
<br />
;[http://www.cs.uu.nl/pub/RUU/CS/techreps/CS-2004/2004-059.pdf Explicit Implicit Parameters]<br />
:A. Dijkstra and S. D. Swierstra. UU-CS 2004-059, 2004.<br />
<br />
==Object oriented Haskell==<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/oo-haskell/index.htm Object-Oriented Style Overloading for Haskell] <br />
:Mark Shields and Simon Peyton Jones; BABEL workshop '01.<br />
<br />
;[http://www.cse.unsw.edu.au/~chak/papers/PC03.html Interfacing Haskell with Object-Oriented Languages]<br />
:Andr T. H. Pang and Manuel M. T. Chakravarty. In Greg Michaelson and Phil Trinder, editors, Implementation of Functional Languages: 15th International Workshop, IFL 2003, Edinburgh, UK, September 8-11, 2003, Revised Papers, LNCS 3145, Springer-Verlag, pages 20-36, 2004. <br />
<br />
;[ftp://ftp.cs.chalmers.se/pub/cs-reports/papers/sparud/haskell++.ps.gz Haskell++: An Object-Oriented Extension of Haskell]<br />
:Jan Sparud and John Hughes. Haskell Workshop 1995<br />
<br />
;[http://homepages.cwi.nl/~ralf/OOHaskell/ Haskell's overlooked object system]<br />
:Oleg Kiselyov and Ralf Lämmel, submitted for journal publication; online since 30 Sep. 2004;<br />
<br />
==Restricted Datatypes==<br />
<br />
;[http://www.cs.chalmers.se/~rjmh/Papers/restricted-datatypes.ps Restricted datatypes]<br />
:John Hughes. 1999 Haskell workshop<br />
<br />
==Patterns==<br />
<br />
;[http://www.cs.yale.edu/homes/tullsen/patterns.ps First Class Patterns]<br />
:Mark Tullsen. Practical Aspects of Declarative Languages, Second International Workshop, PADL 2000. volume 1753 of Lecture Notes in Computer Science. January 2000. <br />
<br />
===Pattern guards===<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/pat.htm Pattern Guards and Transformational Patterns]<br />
:Martin Erwig and Simon Peyton Jones; Haskell Workshop 2000.<br />
<br />
;[http://research.microsoft.com/Users/simonpj/Haskell/guards.html A new view of guards]<br />
:Simon Peyton Jones, April 1997<br />
<br />
===Views===<br />
<br />
;[http://www.haskell.org/development/views.html Views: An Extension to Haskell Pattern Matching]<br />
:Warren Burton, Erik Meijer, Patrick Sansom, Simon Thompson and Phil Wadler.<br />
<br />
;[http://homepages.inf.ed.ac.uk/wadler/papers/view/view.ps.gz Views: A way for pattern matching to cohabit with data abstraction]<br />
:POPL 14 (1987), 307-313.<br />
<br />
==Qualified types==<br />
<br />
;[http://haskell.readscheme.org/servlets/cite.ss?pattern=mpj-jones1994a Qualified Types: Theory and Practice]<br />
:Mark P. Jones. PhD. Thesis. Yale University. November 1994.<br />
<br />
;[http://www.cse.ogi.edu/~mpj/pubs/fpca95.ps Simplifying and Improving Qualified Types]<br />
:Mark P. Jones. FPCA '95: Conference on Functional Programming Languages and Computer Architecture. June 1995.<br />
<br />
;[http://www.cse.ogi.edu/~mpj/pubs/RR-1040.ps Simplifying and Improving Qualified Types]<br />
:Mark P. Jones. Yale University. Research Report YALEU/DCS/RR-1040. June 1994.<br />
<br />
;[http://www.cse.ogi.edu/~mpj/pubs/RR-989.ps Coherence for qualified types]<br />
:Mark P. Jones. Yale University. Research Report YALEU/DCS/RR-989. September 1993. <br />
<br />
;[http://www.cse.ogi.edu/~mpj/pubs/rev-qual-types.ps A theory of qualified types]<br />
:Mark P. Jones. ESOP '92: European Symposium on Programming. Lecture Notes in Computer Science, 582. February 1992. (Cited by 68)<br />
<br />
==Polymorphic recursion==<br />
<br />
;[http://portal.acm.org/citation.cfm%3Fcoll%3DGUIDE%26dl%3DGUIDE%26id%3D169692 Type inference with polymorphic recursion]<br />
:F Henglein - ACM Transactions on Programming Languages and Systems (1993)<br />
<br />
;[http://www.jucs.org/jucs_9_8/practical_type_inference_for/paper.pdf Practical Type Inference for Polymorphic Recursion: an Implementation in Haskell]<br />
:C Vasconcellos, L Figueiredo, C Camarao - Journal of Universal Computer Science, 2003<br />
<br />
;[http://www.dcc.ufmg.br/~camarao/ml0-impl.ps Type Inference for Polymorphic Recursive Definitions: a Specification in Haskell]<br />
:L Figueiredo, C Camarao<br />
<br />
[[Category:Research]]</div>Brecknell