- Haskell-Cafe - Haskell.org

Are type families really this slow, or is this a GHC bug?
by Mike Izbicki 27 Jul '13

27 Jul '13

I'm using the TypeFamilies extension to generate types that are quite large. GHC can handle these large types fine when they are created manually, but when type families get involved, GHC's performance dies. It's doing in quadratic time what looks to me like it should be linear time. I don't know if this is expected behavior, if I'm doing something wrong, or if this is a GHC bug. I've attached a code sample below that demonstrates the problem. Types.hs generates other haskell files. The first parameter is the size of the type (which is type list of that length), and the second specifies which test to run. All tests generate the same type in the end, but some use type families and some don't. Here's an example of running it: These tests show quadratic time when using the type family. I have to increase the context stack size to be greater than the recursion depth of the type family. I don't know if this is a bad sign or to be expected. $ ghc --version The Glorious Glasgow Haskell Compilation System, version 7.6.3 $ ghc Types $ ./Types 200 a > test.hs && time ghc test.hs > /dev/null -fcontext-stack=250 real 0m2.973s $ ./Types 300 a > test.hs && time ghc test.hs > /dev/null -fcontext-stack=350 real 0m6.018s $ ./Types 400 a > test.hs && time ghc test.hs > /dev/null -fcontext-stack=450 real 0m9.995s $ ./Types 500 a > test.hs && time ghc test.hs > /dev/null -fcontext-stack=550 real 0m15.645s Without the type family, I get MUCH better performance: $ ./Types 10000 d > test.hs && time ghc test.hs > /dev/null real 0m2.271s ------------------------ -- Types.hs below ------------------------ import System.Environment code :: Int -> String -> String code i test = concat $ map (++"\n") $ [ "{-# LANGUAGE TypeOperators,DataKinds, KindSignatures,TypeFamilies,PolyKinds #-}" , "import GHC.TypeLits" , "data Nat1 = Zero | Succ Nat1" , "type family Replicate1 (n :: Nat1) (x::a) :: [a]" , "type instance Replicate1 Zero x = '[]" , "type instance Replicate1 (Succ n) x = x ': (Replicate1 n x)" , "class Class a where" , " f :: a -> a" , "data Data (xs::a) = X | Y" , " deriving (Read,Show)" , "main = print test1" ] ++ case head test of 'a' -> [ "instance (xs ~ Replicate1 ("++mkNat1 i++") ()) => Class (Data xs) where" , " f X = Y" , " f Y = X" , "test1 = f (X :: Data ( Replicate1 ("++mkNat1 i++") () ))" ] 'b' -> [ "instance (xs ~ ("++mkList i++") ) => Class (Data xs) where" , " f X = Y" , " f Y = X" , "test1 = f (X :: Data ( Replicate1 ("++mkNat1 i++") () ))" ] 'c' -> [ "instance (xs ~ Replicate1 ("++mkNat1 i++") ()) => Class (Data xs) where" , " f X = Y" , " f Y = X" , "test1 = f (X :: Data ( ("++mkList i++") ))" ] otherwise -> [ "instance (xs ~ ("++mkList i++") ) => Class (Data xs) where" , " f X = Y" , " f Y = X" , "test1 = f (X :: Data ( ("++mkList i++") ))" ] mkList :: Int -> String mkList 0 = " '[] " mkList i = " () ': " ++ mkList (i-1) mkNat1 :: Int -> String mkNat1 0 = " Zero " mkNat1 i = " Succ ( " ++ mkNat1 (i-1) ++ ")" main = do numstr : test : xs <- getArgs let num = read numstr :: Int putStrLn $ code num test

2 2

Sneaky method for var-arg fns?
by Micah Cowan 26 Jul '13

26 Jul '13

So, just for fun, I came up with a way to abuse the language in order to define a "function" whose argument is optional: > -- dirty-trick.hs - A sneaky way to do var args fns in Haskell > > {-# LANGUAGE FlexibleInstances #-} > > class Hello a where > hello :: a > > instance Hello (String -> String) where > hello = (\str -> "Hello " ++ str) > > instance Hello String where > hello = hello "World" In ghci, putStrLn $ hello gives "Hello World", while putStrLn $ hello "There" gives "Hello". . I was wondering if there was a way to do it in "pure" Haskell (i.e., no GHC pragmas required), and also the specific reason for why the above example doesn't work without the pragma (I think it's just that in general a -> b is not syntactically allowed for type specifiers within instance declarations)? I'm also interested in alternative approaches to creating variable-argument functions, if there are any. . If anyone's curious, this was prompted by a discussion with a friend (copied), about Haskell and Clojure. He mentioned that Clojure can accept variable arguments, though AFAICT all Clojure functions basically act like they take a list (that supports variable types), so accepting an empty argument list is a bit analogous to Haskell accepting an empty list, rather than no arguments. Part of the reason Haskell can't really take "variable arguments" is that all Haskell functions really just take one argument. But I figured you could use the contextually expected type to decide whether to return a simple value (not /technically/ a function in that case), or a function expecting further arguments, which could then be extended to define a function taking any arbitrary number of arguments. Cheers! -mjc

4 3

Proposal: Non-recursive let
by oleg＠okmij.org 26 Jul '13

26 Jul '13

Jon Fairbairn wrote: > It just changes forgetting to use different variable names because of > recursion (which is currently uniform throughout the language) to > forgetting to use non recursive let instead of let. Let me bring to the record the message I just wrote on Haskell-cafe http://www.haskell.org/pipermail/haskell-cafe/2013-July/109116.html and repeat the example: In OCaml, I can (and often do) write let (x,s) = foo 1 [] in let (y,s) = bar x s in let (z,s) = baz x y s in ... In Haskell I'll have to uniquely number the s's: let (x,s1) = foo 1 [] in let (y,s2) = bar x s1 in let (z,s3) = baz x y s2 in ... and re-number them if I insert a new statement. I once wrote about 50-100 lines of code with the fragment like the above and the only problem was my messing up the numbering (at one place I used s2 where I should've used s3). In the chain of lets, it becomes quite a chore to use different variable names -- especially as one edits the code and adds new let statements. I have also had problems with non-termination, unintended recursion. The problem is not caught statically and leads to looping, which may be quite difficult to debug. Andreas should tell his story. In my OCaml experience, I don't ever remember writing let rec by mistake. Occasionally I write let where let rec is meant, and the type checker very quickly points out a problem (an unbound identifier). No need to debug anything. Incidentally, time and again people ask on the Caml list why 'let' in OCaml is by default non-recursive. The common answer is that the practitioners find in their experience the non-recursive let to be a better default. Recursion should be intended and explicit -- more errors are caught that way. Let me finally disagree with the uniformity principle. It may be uniform to have equi-recursive types. OCaml has equi-recursive types; internally the type checker treats _all_ types as (potentially) equi-recursive. At one point OCaml allowed equi-recursive types in user programs as well. They were introduced for the sake of objects; so the designers felt uniformly warrants to offer them in all circumstances. The users vocally disagreed. Equi-recursive types mask many common type errors, making them much more difficult to find. As the result, OCaml developers broke the uniformity. Now, equi-recursive types may only appear in surface programs in very specific circumstances (where objects or their duals are involved). Basically, the programmer must really intend to use them. Here is an example from the natural language, English. Some verbs go from regular (uniform conjugation) to irregular: http://en.wiktionary.org/wiki/dive

19 40

Fwd: News: FP Complete Offering Free Academic Accounts to FP Haskell Center
by Natalia Muska 25 Jul '13

25 Jul '13

FP Complete Offering Free Academic Accounts to FP Haskell Center San Diego, C.A. (July 25, 2013) FP Complete, the leading developer of commercial Haskell software tools and services, announced today that professors and students will be offered free accounts to FP Haskell Center, the world’s first commercial Haskell IDE and deployment platform. FP Haskell Center is an integrated development and deployment environment written in Haskell, the most popular and purest functional programming language. It consists of two components, the FP Development Environment and the FP Application Server. The FP Development Environment includes a Haskell compiler and a continually updated set of vetted, tested and supported libraries and code templates. There is no need to run Cabal or other installers. The FP Application Server is used to deploy and run Haskell applications directly in the cloud. With many tutorials and sample code included in the product, FP Haskell Center provides both teachers and students with an accessible cloud-based platform to teach/learn, perform Haskell research, and develop real-world solutions. “Haskell was created at some leading universities in the world over 20 years ago and its advancement since then has been significantly driven by the global academic community,” said Aaron Contorer, FP Complete founder and CEO. “As Haskell becomes more mainstream, we want to provide the institutions championing Haskell the most the opportunity to keep it growing at no cost to them” he adds. “Great things are constantly coming out of the university setting and we want to support their research and projects as much as we can.” Eligible teachers and students can get a free account through a simple web sign-up form in mid-August, right before FP Haskell Center becomes generally available in early September. They can get started now by signing up <https://learning-site-staging.fpcomplete.com/business/designer-ide> for a Beta. Check for updates/details at www.fpcomplete.com. About FP Complete FP Complete is dedicated to bringing the Haskell programming language into the mainstream software market by being the leading developer of commercial Haskell software tools and services. Haskell is the new way to make software that accelerates time to market, boosts programmer productivity, lowers cost, and increases product quality. Haskell enables rapid development of high-performing, complex software with high quality, maintainability and scalability. Haskell has proven to be able to significantly cut the billions wasted in the compile- test-debugging-rework cycles where 50% of the software project costs are today. In short, Haskell delivers the competitive advantage and productivity that enterprises need in a global software-driven economy. Visit www.fpcomplete.com for more information. -- Natalia Muska Marketing Manager FP Complete, Inc. Natalia(a)fpcomplete.com 865-506-6513 skype: natalia.s.muska

1 0

Re: [Haskell-cafe] Proposal: Non-recursive let
by oleg＠okmij.org 25 Jul '13

25 Jul '13

ivan.chollet wrote: > let's consider the following: > > let fd = Unix.open ... > let fd = Unix.open ... > > At this point one file descriptor cannot be closed. Static analysis will > have trouble catching these bugs, so do humans. Both sentences express false propositions. The given code, if Haskell, does not open any file descriptors, so there is nothing to close. In the following OCaml code let fd = open_in "/tmp/a" in let fd = open_in "/tmp/v" in ... the first open channel becomes unreachable. When GC collects it (which will happen fairly soon, on a minor collection, because the channel died young), GC will finalize the channel and close its file descriptor. The corresponding Haskell code do h <- openFile ... h <- openFile ... works similarly to OCaml. Closing file handles upon GC is codified in the Haskell report because Lazy IO crucially depends on such behavior. If one is interested in statically tracking open file descriptors and making sure they are closed promptly, one could read large literature on this topic. Google search for monadic regions should be a good start. Some of the approaches are implemented and used in Haskell. Now about static analysis. Liveness analysis has no problem whatsoever determining that a variable fd in our examples has been shadowed and the corresponding value is dead. We are all familiar with liveness analysis -- it's the one responsible for `unused variable' warnings. The analysis is useful for many other things (e.g., if it determines that a created value dies within the function activation, the value could be allocated on stack rather than on heap.). Here is example from C: #include <stdio.h> void foo(void) { char x[4] = "abc"; /* Intentional copying! */ { char x[4] = "cde"; /* Intentional copying and shadowing */ x[0] = 'x'; printf("result %s\n",x); } } Pretty old GCC (4.2.1) had no trouble detecting the shadowing. With the optimization flag -O4, GCC acted on this knowledge. The generated assembly code reveals no traces of the string "abc", not even in the .rodata section of the code. The compiler determined the string is really unused and did not bother even compiling it in. > Disallowing variable shadowing prevents this. > The two "fd" occur in different contexts and should have different names. > Usage of shadowing is generally bad practice. It is error-prone. Hides > obnoxious bugs like file descriptors leaks. > The correct way is to give different variables that appear in different > contexts a different name, although this is arguably less convenient and > more verbose. CS would be better as science if we refrain from passing our personal opinions and prejudices as ``the correct way''. I can't say better than the user Kranar in a recent discussion on a similar `hot topic': The issue is that much of what we do as developers is simply based on anecdotal evidence, or statements made by so called "evangelicals" who blog about best practices and people believe them because of how articulate they are or the cache and prestige that the person carries. ... It's unfortunate that computer science is still advancing the same way medicine advanced with witch doctors, by simply trusting the wisest and oldest of the witch doctors without any actual empirical data, without any evidence, just based on the reputation and overall charisma or influence of certain bloggers or "big names" in the field. http://www.reddit.com/r/programming/comments/1iyp6v/is_there_a_really_an_em…

3 2

Re: [Haskell-cafe] Parsec question
by Kashyap CK 25 Jul '13

25 Jul '13

There is reference in the paper that empty list indicates failure...so could we just use it like Maybe? I'd like it very much if I could get an example of a missed match by not using the complete match. regards, Kashyap Sent from my Windows Phone From: Roman Cheplyaka Sent: 24/07/2013 8:19 PM To: C K Kashyap Cc: Haskell Cafe Subject: Re: [Haskell-cafe] Parsec question Think about this: if you always take only the first element, why do you need lists at all? Roman * C K Kashyap <ckkashyap(a)gmail.com> [2013-07-24 19:56:29+0530] > Dear Cafe, > > I am trying to implement[1] parsec in go using the "Monadic Parser > Combinators" paper [2] . I've been able to implement "plus" "bind" and > "many" > While doing the implementation - I looked at bind closely > > bind :: Parser a -> (a -> Parser b) -> Parser b > p `bind` f = \inp -> concat [f v inp' | (v,inp') <- p inp] > > I wondered if the result needs the complete list - wouldn't just the first > successful value suffice? > Perhaps - > p `bind` f = \inp -> take 1 $ concat [f v inp' | (v,inp') <- p inp] > > Will this miss out matches? > > > Regards, > Kashyap > > [1] https://github.com/ckkashyap/parsec/blob/master/parsec.go > [2] Monadic Parser Combinators: Graham Hutton, Erik Meijer > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe

3 2

Parsec question
by C K Kashyap 25 Jul '13

25 Jul '13

Dear Cafe, I am trying to implement[1] parsec in go using the "Monadic Parser Combinators" paper [2] . I've been able to implement "plus" "bind" and "many" While doing the implementation - I looked at bind closely bind :: Parser a -> (a -> Parser b) -> Parser b p `bind` f = \inp -> concat [f v inp' | (v,inp') <- p inp] I wondered if the result needs the complete list - wouldn't just the first successful value suffice? Perhaps - p `bind` f = \inp -> take 1 $ concat [f v inp' | (v,inp') <- p inp] Will this miss out matches? Regards, Kashyap [1] https://github.com/ckkashyap/parsec/blob/master/parsec.go [2] Monadic Parser Combinators: Graham Hutton, Erik Meijer

3 3

How can I use ghci more wisely?
by yi lu 25 Jul '13

25 Jul '13

I am wondering how can I ask ghci to show an infinite list wisely. When I type *fst ([1..],[1..10])* The result is what as you may guess *1,2,3,4,...*(continues to show, cut now) How could I may ghci show *[1..]* this wise way not the long long long list itself? Yi

6 6

Expression problem in the database?
by Manuel Gómez 24 Jul '13

24 Jul '13

Hi café, I don’t know whether this is a good forum to ask about this —perhaps Stack Overflow is better suited—, but since Haskell and related languages are so finely fit for good solutions to the expression problem, I figure this list may have a few helpful pointers regarding this problem. I’m facing a situation that requires saving boolean expressions of more or less arbitrary structure (encoding some business rules) into a SQL database. The expressions can include terms that refer to some other objects in the database. I realize this is somewhat vague, but that’s intentional: I’m really searching for ideas and experience with similar problems, not for a specific solution to my specific situation. Though I’m uncertain of their relative merits, I’ve had a few ideas myself: * I could sacrifice relational integrity and store the expression serialized, perhaps as an AST represented in JSON or somesuch — although the rest of the data model is a rather traditional, normalized relational schema, so this is undesirable in my situation if only for consistency. * I could directly model some form of the expression’s AST in the relational schema, and then endure the usual pain of representing sum types as relations. I imagine this to be quite unpleasant, although I haven’t tried it. * As these are boolean logic predicates, the expressions could be transformed into some normal form that could be more easily represented with relations. I’ll be mostly (but not exclusively) using this database from an application written in Haskell (Yesod using Esqueleto to talk to PostgreSQL), so some native Haskell solution could work almost as well as an SQL solution — but some legacy systems do need to interact with the database, so I’d prefer a solution in the database as long as it’s not horrible to work with in the application. I’ll be grateful for any ideas or pointers — my Googling for the expression problem has not proved fruitful. Thanks!

3 3

memoization
by Christopher Howard 24 Jul '13

24 Jul '13

When I previously asked about memoization, I got the impression that memoization is not something that just happens magically in Haskell. Yet, on a Haskell wiki page about Memoization <http://www.haskell.org/haskellwiki/Memoization#Memoization_with_recursion>, an example given is memoized_fib :: Int -> Integer memoized_fib = (map fib [0 ..] !!) where fib 0 = 0 fib 1 = 1 fib n = memoized_fib (n-2) + memoized_fib (n-1) I guess this works because, for example, I tried "memoized_fib 10000" and the interpreter took three or four seconds to calculate. But every subsequent call to "memoized_fib 10000" returns instantaneously (as does "memoized_fib 10001"). Could someone explain the technical details of why this works? Why is "map fib [0 ..]" not recalculated every time I call memoized_fib?

6 12