December 2013 - Haskell-Cafe

Re: [Haskell-cafe] Constraint-folding
by oleg＠okmij.org 03 Dec '13

03 Dec '13

Andras Slemmer wrote: > I stumbled upon something pretty neat, and although I'm 95% sure Oleg did > this already 10 years ago in Haskell98 You're quite right about this: Chung-chieh Shan and I did this reification of constraint in December 2003, and almost in Haskell 98 (we needed Rank2 types though). It was described in the following paper http://okmij.org/ftp/Haskell/types.html#Prepose We called this transformation reflection/reification. I'm writing though to show a dual formulation to your development of using singletons. It gets by without GADTs and uses very few extensions: essentially Haskell98 with Rank2 types. {-# LANGUAGE RankNTypes #-} data Zero data Succ a class Class n instance Class Zero instance (Class m) => Class (Succ m) -- Tagless final class Sym repr where z :: repr Zero s :: repr n -> repr (Succ n) newtype R x = R{unR:: x} -- the identity interpreter instance Sym R where z = R undefined s _ = R undefined newtype S x = S Integer -- for show instance Sym S where z = S 0 s (S x) = S (x + 1) newtype Reify n = Reify (forall a. (Class n => n -> a) -> a) instance Sym Reify where z = Reify (\f -> f (unR z)) s (Reify f) = Reify (\g -> f (g . unR . s . R)) genericClass :: (forall repr. Sym repr => repr n) -> (Class n => a) -> a genericClass m f = case m of Reify k -> k (const f)

1 0

The rmonad package is mysterious
by Simon Marechal 03 Dec '13

03 Dec '13

I tried to do something simple using the rmonad package (attached). I followed the example that's in haddocks (it is wrong, constraints has no arguments), grabbed the list of extensions from rmonad's source, but this program doesn't typecheck: Could not deduce (Hashable a) arising from a use of `HM.singleton' This seems to be an obvious use of this package ... am I missing something ?

2 1

how to factorize propagation of a function over a data type
by TP 02 Dec '13

02 Dec '13

Hi, Let us consider the following example: ----------------------- class FooClass a where foo1 :: a -> a foo2 :: a -> a instance FooClass Integer where foo1 v = 1 foo2 v = 2 data Bar = Bar1 Integer | Exp1 Bar Bar | Exp2 Bar Bar deriving Show instance FooClass Bar where foo1 b = case b of Bar1 i -> Bar1 (foo1 i) Exp1 b1 b2 -> Exp1 (foo1 b1) (foo1 b2) Exp2 b1 b2 -> Exp2 (foo1 b1) (foo1 b2) foo2 b = case b of Bar1 i -> Bar1 (foo2 i) Exp1 b1 b2 -> Exp1 (foo2 b1) (foo2 b2) Exp2 b1 b2 -> Exp2 (foo2 b1) (foo2 b2) main = do let a = Bar1 3 let b = Bar1 4 let c = Exp1 (Exp2 a b) b print c print $ foo1 c print $ foo2 c ----------------------- We obtain as expected: $ runghc propagate_with_duplicated_code.hs Exp1 (Exp2 (Bar1 3) (Bar1 4)) (Bar1 4) Exp1 (Exp2 (Bar1 1) (Bar1 1)) (Bar1 1) Exp1 (Exp2 (Bar1 2) (Bar1 2)) (Bar1 2) My question is related to the code inside the Fooclass instance definition for Bar: we have repeated code where only "foo1" or "foo2" changes. So the first idea is to write a higher-order function, but it does not work: ----------------------- class FooClass a where foo1 :: a -> a foo2 :: a -> a instance FooClass Integer where foo1 v = 1 foo2 v = 2 data Bar = Bar1 Integer | Exp1 Bar Bar | Exp2 Bar Bar deriving Show propagate :: FooClass a => a -> (a->a) -> a propagate v f = case v of Bar1 i -> Bar1 (f i) Exp1 b1 b2 -> Exp1 (f b1) (f b2) Exp2 b1 b2 -> Exp2 (f b1) (f b2) instance FooClass Bar where foo1 b = propagate b foo1 foo2 b = propagate b foo2 main = do let a = Bar1 3 let b = Bar1 4 let c = Exp1 (Exp2 a b) b print c print $ foo1 c print $ foo2 c ----------------------- The problem is that the type variable `a` in the definition of `propagate` cannot match both the type of i, i.e. an integer, and the type of b1 and b2, i.e. Bar. Putting the function propagate in the typeclass does not help. How to factorize my code? Thanks in advance, TP

6 10

Type-level case
by Mike Ledger 02 Dec '13

02 Dec '13

Hi. This is more of a brain dump than anything well thought out, but it's been in the back of my mind for a while. It's occurred to me that with the upcoming release of GHC 7.8, which features closed type families, we've effectively been given type-level pattern matching that behaves the same as expression-level pattern matching. What I think could follow is type-level case syntax. For example: type family Example a where Example 100 = 60 Example 120 = 15 Example x = x * 30 contrived :: Sing a -> Sing b -> Sing (Example (a+b)) might instead be expressed as: contrived :: Sing a -> Sing b -> Sing (case a+b of 100 -> 60 120 -> 15 x -> x*30) -- but with something other than -> in the patterns, -- since that conflicts with the type (->), and there -- are probably too many arrows already Similarly I think if-then-else could be lifted to the type level, also. Some problems with this are that it could pollute "complex" type signatures even further (although currently the situation isn't very good due to haddock/ghc not listing type family instances), and it would get quite cumbersome quickly to have to type out contrived2 :: Proxy (a, b) -> Sing (case a+b of { 100 -> 60; 120 -> 15; x -> x*30 }) -> ... -- Mike

2 1

PhD position at Ghent University
by Tom Schrijvers 02 Dec '13

02 Dec '13

The Programming Languages Group of Ghent University (UGent) invites applicants for a PhD position on the project Reasoning about Coroutines under the direction of Tom Schrijvers. The project concerns reasoning techniques (like type systems and program analysis) for coroutines in its many forms (like delimited continuations and effect handlers). It is conducted in collaboration with the declarative languages group of KU Leuven university and our international partners. We seek applicants at an international level of excellence. As a successful applicant, you have a master degree in Computer Science or equivalent. Ideally, you also have a strong, documented interest in doing research. Strong problem-solving and programming skills are essential. Prior knowledge of functional programming, logic programming, type systems or program analysis are an advantage. The PhD position is for 4 years and starts between January and October 2014. The position is fully funded by the Fund for Scientific Research Flanders (FWO). The salary is compatible with other Belgian PhD rates and among the better ones in Europe and abroad. You will become part of UGent's dynamic and growing Programming Languages Group. UGent is one of the major universities in the Dutch-speaking region of Europe. It distinguishes itself as a socially committed and pluralistic university in a broad international perspective. Our university is located in the beautiful city of Ghent, which is one of Europe’s greatest discoveries, according to Lonely Planet. Please direct your inquiries and applications by e-mail to Tom Schrijvers < tom.schrijvers(a)ugent.be>, principal investigator on this project. To apply, send as soon as possible: 1) a letter of interest (including motivation relevant to the research topic), 2) your detailed curriculum vitae (including study curriculum rankings, relevant research experience and publications), 3) your diploma and transcripts (including translation if possible). We will determine the start date together with the selected candidate. See here for more information: * http://users.ugent.be/~tschrijv/phdposition3.html * http://users.ugent.be/~tschrijv/research.html * http://www.ugent.be/en/research/doctoralresearch -- prof. dr. ir. Tom Schrijvers Programming Languages Group Department of Applied Mathematics and Computer Science University of Ghent Krijgslaan 281 S9 9000 Gent Belgium Phone: +32 9 264 4805 http://users.ugent.be/~tschrijv/

1 0

Call for Papers: 15th Symposium on Trends in Functional Programming, May 2014, Utrecht
by Simon Thompson 02 Dec '13

02 Dec '13

----------------------------- C A L L F O R P A P E R S ----------------------------- ======== TFP 2014 =========== 15th Symposium on Trends in Functional Programming May 26-28, 2014 Utrecht University Soesterberg, The Netherlands http://www.cs.uu.nl/wiki/TFP2014/WebHome The symposium on Trends in Functional Programming (TFP) is an international forum for researchers with interests in all aspects of functional programming, taking a broad view of current and future trends in the area. It aspires to be a lively environment for presenting the latest research results, and other contributions (see below), described in draft papers submitted prior to the symposium. A formal post-symposium refereeing process then selects a subset of the articles presented at the symposium and submitted for formal publication. Selected papers will be published as a Springer Lecture Notes in Computer Science (LNCS) volume. TFP 2014 will be the main event of a pair of functional programming events. The other is the International Workshop on Trends in Functional Programming in Education (TFPIE). TFPIE will take place on May 25th. The TFP symposium is the heir of the successful series of Scottish Functional Programming Workshops. Previous TFP symposia were held in Edinburgh (Scotland) in 2003, in Munich (Germany) in 2004, in Tallinn (Estonia) in 2005, in Nottingham (UK) in 2006, in New York (USA) in 2007, in Nijmegen (The Netherlands) in 2008, in Komarno (Slovakia) in 2009, in Oklahoma (USA) in 2010, in Madrid (Spain) in 2011, St. Andrews (UK) in 2012 and Provo (Utah, USA) in 2013. For further general information about TFP please see the TFP homepage. INVITED SPEAKERS TFP is pleased to announce talks by the following two invited speakers: John Hughes of Chalmers, Goteborg, Sweden, is well-known as author of Why Functional Programming Matters, and as one of the designers of QuickCheck (together with Koen Claessen); the paper on QuickCheck won the ICFP Most Influential Paper Award in 2010. Currently he divides his time between his professorship and Quviq, a company that performs property-based testing of software with a tool implemented in Erlang. Dr. Geoffrey Mainland received his PhD from Harvard University where he was advised by Greg Morrisett and Matt Welsh. After a two year postdoc with the Programming Principles and Tools group at Microsoft Research Cambridge, he is now an assistant professor at Drexel University. His research focuses on high-level programming language and runtime support for non-general purpose computation. SCOPE The symposium recognizes that new trends may arise through various routes. As part of the Symposium's focus on trends we therefore identify the following five article categories. High-quality articles are solicited in any of these categories: Research Articles: leading-edge, previously unpublished research work Position Articles: on what new trends should or should not be Project Articles: descriptions of recently started new projects Evaluation Articles: what lessons can be drawn from a finished project Overview Articles: summarizing work with respect to a trendy subject Articles must be original and not submitted for simultaneous publication to any other forum. They may consider any aspect of functional programming: theoretical, implementation-oriented, or more experience-oriented. Applications of functional programming techniques to other languages are also within the scope of the symposium. Topics suitable for the symposium include: Functional programming and multicore/manycore computing Functional programming in the cloud High performance functional computing Extra-functional (behavioural) properties of functional programs Dependently typed functional programming Validation and verification of functional programs Using functional techniques to reason about imperative/object-oriented programs Debugging for functional languages Functional programming in different application areas: security, mobility, telecommunications applications, embedded systems, global computing, grids, etc. Interoperability with imperative programming languages Novel memory management techniques Program analysis and transformation techniques Empirical performance studies Abstract/virtual machines and compilers for functional languages (Embedded) domain specific languages New implementation strategies Any new emerging trend in the functional programming area If you are in doubt on whether your article is within the scope of TFP, please contact the TFP 2014 program chair, Jurriaan Hage at J.Hage(a)uu.nl. BEST PAPER AWARDS To reward excellent contributions, TFP awards a prize for the best paper accepted for the formal proceedings. TFP traditionally pays special attention to research students, acknowledging that students are almost by definition part of new subject trends. A student paper is one for which the authors state that the paper is mainly the work of students, the students are listed as first authors, and a student would present the paper. A prize for the best student paper is awarded each year. In both cases, it is the PC of TFP that awards the prize. In case the best paper happens to be a student paper, that paper will then receive both prizes. SPONSORS TFP is financially supported by NWO (Netherlands Organisation for Scientific Research), Well-Typed and Erlang Solutions. PAPER SUBMISSIONS Acceptance of articles for presentation at the symposium is based on a lightweight peer review process of extended abstracts (4 to 10 pages in length) or full papers (16 pages). The submission must clearly indicate which category it belongs to: research, position, project, evaluation, or overview paper. It should also indicate whether the main author or authors are research students. In the case of a full student paper, the paper will receive additional feedback by one of the PC members shortly after the symposium has taken place. We shall use EasyChair for the refereeing process. IMPORTANT DATES Submission of draft papers: March 17, 2014 Notification: March 24, 2014 Registration: April 7, 2014 TFP Symposium: May 26-28, 2014 Student papers feedback: June 9th, 2014 Submission for formal review: July 1st, 2014 Notification of acceptance: September 8th, 2014 Camera ready paper: October 8th, 2014 PROGRAM COMMITTEE Peter Achten Radboud University Nijmegen Emil Axelsson Chalmers Lucilia Camarao de Figueiredo Universidade Federal de Ouro Preto Laura Castro University of A Coruna Frank Huch Christian-Albrechts-University of Kiel Matthew Fluet Rochester Institute of Technology Jurriaan Hage (chair) University of Utrecht Yukiyoshi Kameyama University of Tsukuba Andrew Kennedy Microsoft Research Tamas Kozsik Eotvos Lorand University Ben Lippmeier University of New South Wales Luc Maranget INRIA Jay McCarthy Brigham Young University Marco T. Morazan Seton Hall University Ricardo Pena Universidad Complutense de Madrid Alexey Rodriguez madvertise Sven-Bodo Scholz Heriot-Watt University Manuel Serrano INRIA Sophia Antipolis Simon Thompson University of Kent Tarmo Uustalu Inst of Cybernetics David Van Horn Maryland University Janis Voigtlaender University of Bonn Simon Thompson | Professor of Logic and Computation School of Computing | University of Kent | Canterbury, CT2 7NF, UK s.j.thompson(a)kent.ac.uk | M +44 7986 085754 | W www.cs.kent.ac.uk/~sjt

1 0

Looking for reliable heterogeneous vectors
by Sergey Bushnyak 01 Dec '13

01 Dec '13

Hello, everyone. I'm looking for reliable library or idea how to implement heterogenous vector properly. It may seem odd, but I want elements not only be different types but also functions, something like that, pseudocode: hvec [a b (c->d) [a] ...] -- can be any type let hvec = hvec [ "stuff" 5 getUrl [1, 4, 5]] So far I found *vector-heterogenous* package, but can't decide is it good to build on or create something on my own. Any thoughts and ideas are appreciated. Thanks.

4 7

possible CS major seeking advice
by Dennis Raddle 01 Dec '13

01 Dec '13

Sort of off-topic for Haskell, just seeking general advice. (I do love Haskell.) I'm 45, have a B.S. from Caltech and 20+ years of programming experience with NASA (JPL), and now I'm thinking of going back to school to get a Ph.D. in computer science, with a goal of teaching at the university level. I'd like some advice about a possible path. Currently I have an illness which prevents me from handling full-time school, and I am receiving a small disability income. That's the bad news; the good news is that it looks like recovery is on the horizon, perhaps a few years out. Getting admitted to graduate school poses a problem. The only people who know my recent work are my supervisors at NASA. My work at NASA was very uncreative, just grinding through boring code. I was getting gradually sicker and my productivity was going down. Then I got laid off. I'm sure they weren't happy with my productivity. So I'm not too optimistic about getting a glowing letter from my direct boss. However, I did work with two scientists there--they were project leaders, not my boss--and I made a good impression. It's been something like five years since I worked with them and I don't know how well they will remember, but I think they would give me good letters if I can locate them and they remember me. Another possible good letter would come from a fellow I know with a Ph.D. in mathematics. We have worked closely over the years on something very hard to describe called the Feldenkrais Method. It's not math or computer science, but it does require a lot of creativity and learning about learning. I have demonstrated dedication, focus, and intelligence in my work with him. He could give me a good letter, but it's questionable how well it would be received as it's not about CS directly. Another path would be to attend a local state college first and have some professors get to know me, then get letters from them. I'm near California State University Northridge and California State University LA. I hope I could easily get admitted to the M.S. program there. I have some prerequisites to get out of the way; my CS classes at Caltech include only half the normal B.S. requirements, and I am rusty at many things (discrete mathematics, calculus, formal logic, etc.--never used any of these in my job and it's been 20+ years). Although clearly full-time school is out of the question for a few years, I could attend part-time and take some of these prerequisites. For both my M.S. and Ph.D. I want to get admitted to the very best school I can. I'm sure the school determines much of the career that follows. So I would not want to finish the M.S. at the California State schools, but rather transfer to somewhere more prestigious eventually. My next problem is determining an area of specialization. As a professor, I think it's the teaching and mentoring that will satisfy me the most. To feel good about my job I need to work with people and not stick my nose in a computer screen all the time. If I can find a job with good teaching and mentoring opportunities, I know I will LOVE it. I will talk all the time about the pleasure of having a job I love. I'll want to get up in the morning (and that was a big problem with my job at JPL; I was getting depressed). But what will be my area of specialization? As an undergrad I was most drawn to discrete mathematics and algorithms. I also love learning Haskell and would probably be interested in languages. I never really connected with any other classes. But should I specialize in algorithms or languages? I don't know. A priority for me is interacting with people collaboratively, so it might be good to specialize in an area that gets me out in the practical world sometimes. Maybe artificial intelligence? I'm even thinking about the intersection of C.S. and teaching, like devising programs that help teach mathematics and CS through artificial intelligence. But I don't know about artificial intelligence in particular. I would be interested in hearing what people think about areas of CS that would get me involved in real-world applications. Although teaching is my passion, it would be good to stay open to a job in industry should that become desirable for financial reasons. I'm poor right now, have little retirement savings, and I'm blowing through them quickly due to the high medical costs I have. Although people say, "Do what you love, the money will follow." I wonder if those people have ever been poor, especially sick and poor. At some point money becomes more important. But my first preference is teaching. I just don't want to close any doors. Any advice welcome, Dennis

2 1

Re: [Haskell-cafe] possible CS major seeking advice
by Dennis Raddle 01 Dec '13

01 Dec '13

Michal, But I'm not "better than them." My job didn't involve any CS, and my prior coursework represents only through about the junior year. I want the whole experience of a Ph.D., especially getting mentored. An earned Ph.D. also seems to give me the best job options. That's my thought, anyway. Dennis On Sun, Dec 1, 2013 at 2:00 PM, MJG <mjgajda(a)gmail.com> wrote: > Dear Dennis, > > What about old-fashioned attempt to pass PhD exams that some schools ? > Or take online courses for the last year in the domain that you plan to > complete your PhD in, just to prove that you're as good, or better than > their students? > > I believe you're not the only one that tries to complete PhD later than > most students. (I think late mr. Jobs had a similar idea to stress out > after being kicked out of his own company.) > -- > Best regards > Michal > >

1 0

Constraint-folding
by Andras Slemmer 01 Dec '13

01 Dec '13

Hi, I stumbled upon something pretty neat, and although I'm 95% sure Oleg did this already 10 years ago in Haskell98 I thought I'd share it because I find it gorgeous! The basic issue I was having is that whenever I wrote class instances for a lifted type (we'll use Nat): class Class (n :: Nat) instance Class Zero instance (Class m) => Class (Succ m) I always had to litter my code with "(Class n) =>" restrictions even in places where they just shouldn't belong. However my gut feeling was that the generic instance "should" be implied, as we covered all cases. A while ago I proposed a new syntax to do just this ( https://ghc.haskell.org/trac/ghc/ticket/6150) which failed miserably, and for good reason! However there is a way to do it anyway:) What we need is basically a way to "construct" an instance for the fully polymorpic case: "instance Class n". We cannot do this directly as it would overlap with our original instances (and we couldn't implement it anyway), we need another way of representing class instances: type W p = forall a. (p => a) -> a W p simply "wraps" the constraint p into a function that eliminates the constraint on a passed in value. Now we can treat a constraint as a function. We will also need a way to "pattern match" on our lifted types, we will do this with an indexed GADT: data WNat n where -- W for Witness WZero :: WNat Zero WSucc :: WNat n -> WNat (Succ n) And finally the neat part; one can write a general typeclass-polymorphic induction principle on these wrapped constraints (or a "constraint-fold"): natFold :: WNat n -> W (p Zero) -> (forall m. W (p m) -> W (p (Succ m))) -> W (p n) W (p Zero) in the p ~ Class case corresponds to "instance Class Zero", and (forall m. W (p m) -> W (p (Succ m))) corresponds to "instance (Class m) => Class (Succ m)" This function is precisely what we need in order to construct the generic instance! (Note: the implementation of natFold is NOT trivial as we need to wrestle with the type checker in the inductive case, but it is a nice excercise. The solution is here: http://lpaste.net/96429) Now we can construct the generic instance: genericClass :: WNat n -> (Class n => a) -> a genericClass n = natFold n (\x -> x) (\f x -> f x) -- Cannot use id as that would try to unify away our constraints Or equivalently: class WNatClass n where witness :: WNat n instance WNatClass Zero where witness = WZero instance (WNatClass m) => WNatClass (Succ m) where witness = WSucc witness genericClass' :: (WNatClass n) => (Class n => a) -> a genericClass' = genericClass witness Now we can decouple all our "(Class n) =>" and similar constraints, all we need is a WNatClass restriction, which I think is a good enough trade-off (and it's not really a restriction anyway). What do you think? ex

2 2