October 2008 - Haskell-Cafe

Re: [Haskell-cafe] A question about constraints
by Luke Palmer 03 Oct '08

03 Oct '08

On Thu, Oct 2, 2008 at 7:51 AM, jean-christophe mincke <jeanchristophe.mincke(a)gmail.com> wrote: > Hello, > > Thank you for your comments. > > Would not it be feasible to add constraints at type definition, something > like, in a somewhat free style syntax > > data String2 = String2 (s::String) with length s <= 5 > > and with a polymorphic type > > data List5 a= List5 (l::[a]) with length l <= 5 Well, yeah, it is possible that to a language. However, it's a question of how far you take it. What do you want that to do? Is it a runtime check on the constructor? Is it a compile-time guarantee? If it's runtime, how lazy is it -- i.e. when does it check? If it's compile-time, how do you enforce it? Basically it dumps the contents of pandora's box all over the design space, so it's easier to leave it out and just let module abstraction take care of the hard questions. There are definitely ways to simulate it: You can simulate the runtime checks as follows: subtype :: (a -> Bool) -> (a -> b) -> a -> b subtype p f x = if p x then f x else error "Subtype constraint failed" string2 :: String -> String2 string2 = subtype (\s -> length s < 5) String2 -- And don't expose String2 from the module, so string2 is the only way to make them But to give an example of why this is not a straightforward thing to answer, here's a different way which might also be correct, depending on what you want: string2 :: String -> String2 string2 s = partial 5 s where partial 0 _ = error "Subtype constraint failed" partial n [] = [] partial n (x:xs) = x:partial (n-1) xs Which lazily checks the constraint; i.e. only errors if a value is demanded beyond the index 5 and exists. Implementing Compile-time checks is typically much harder, and demands a bit more cleverness, since the way you do it is different for each type of constraint you have. For this example, you could create an algebra of lengthed lists: import Prelude hiding (++) -- Type level numbers; Z = 0, S n = n + 1. data Z data S n -- Lists of length exactly n data Listn n a where Nil :: Listn Z a Cons :: a -> Listn n a -> Listn (S n) a -- Type-level addition of numbers type family Plus m n :: * type instance Plus Z n = n type instance Plus (S m) n = S (Plus m n) -- Typed append; appends the lists, adds the lengths. -- The compiler verifies that the implementation actually does this! (++) :: Listn m a -> Listn n a -> Listn (Plus m n) a Nil ++ ys = ys Cons x xs ++ ys = Cons x (xs ++ ys) -- Type-level less than or equal; represents the type of *proofs* that m <= n. data m :<= n where LeN :: n :<= n LeS :: m :<= n -> m :<= S n -- A List5 a is a function which takes a proof than n <= 5, and returns a Listn n a type List5 a = forall n. n :<= S (S (S (S (S Z)))) -> Listn n a So that was a bit of work, wasn't it? But this solution is quite expressive; the compiler will not even compile your code if you try to construct a list with more than 5 elements. Furthermore, you can actually write most things you'd expect to because of Haskell's great GADT typechecking features :-) The downside is that you have to redefine all the standard list operations, because, well, they have different types now. The above is approaching what dependently typed languages do. My favorite is Coq (a lot of haskell folks like Agda 2), and in it you can express directly the constraint you want without all this type boilerplate: Definition List5 a := { l : List a | length l <= 5 }. But internally it is doing something very similar to the above Haskell program. This also has the property that it is impossible to write a well-typed program that constructs a List5 of length > 5. In addition, you can use all the standard list functions, however you have to prove what they do to the constraint: Theorem append_length : forall m n a (xs ys : List a), (length xs <= m) -> (length ys <= n) -> (length (xs ++ ys) <= m+n). (* prove prove prove.... *) Qed. And then you can use that theorem to prove that the parts of your program that use List5 are well-typed. Whew, so now that we're done with that, in summary, it depends on your situation how you want to do it, and there's really no "easy answer". I hope you got something out of seeing these techniques. Adding notation like that you suggest is a challenge for the language, since a runtime constraint changes the strictness properties of the object, and a compile-time constraint written that concisely actually does require full dependent types. Best to leave it to the users. Luke

1 0

SCGI module
by Anton Tayanovskyy 02 Oct '08

02 Oct '08

Hello, SCGI module from Hackage is not working for me with Apache mod_scgi, I think because it uses LazyBytestring to hGetContents on a socket handle and the Apache side does not close the socket. Also, looking at the source I didn't see any fork* calls, so I assume it is not doing concurrency. So I ended up writing a replacement and would like to invite comments. It does forkIO per request and, if asked to, timeouts those threads. So far it works for me on simple examples from http://www.haskell.org/haskellwiki/Practical_web_programming_in_Haskell giving roughly 800 requests a second versus 250 on plain CGI (both through Apache). http://hpaste.org/10842 Thanks! Also, in general, is there any interest in using SCGI, or FastCGI (plain CGI, HappS, you name it) is vastly superior? --Anton

2 1

Alex and Flex
by Manlio Perillo 02 Oct '08

02 Oct '08

Hi. I'm starting to write a CSS parser with Alex and Happy. The grammar is defined here: http://www.w3.org/TR/CSS21/grammar.html However I have noted that there are some difference in the syntax between Alex and Flex? What is the rationale? One more thing. Here: http://www.haskell.org/alex/doc/html/alex-files.html it seems that there is an error with macrodef := @smac '=' set | @rmac '=' regexp it should be macrodef := $smac '=' set | @rmac '=' regexp Thanks Manlio Perillo

1 0

Climbing up the shootout...
by Don Stewart 02 Oct '08

02 Oct '08

Thanks to those guys who've submitted parallel programs to the language benchmarks game, we're climbing up the rankings, now in 3rd, and ahead of C :) http://shootout.alioth.debian.org/u64q/benchmark.php?test=all&lang=all Just one or two more parallel programs required... Submit them here, and we can test on quad core, http://haskell.org/haskellwiki/Shootout/Parallel -- Don

24 73

System.Process
by Andrew Coppin 02 Oct '08

02 Oct '08

Much hair-pulling resulted today when I attempted to perform a small task. The System.Process module provides the runCommand function. This takes a complete command line and returns a ProcessHandle. No problem there. The module also provides the runProcess function, which enables you to set environment variables and so forth. However... this doesn't take a complete command line. It takes a path to an executable and a list of parsed arguments. Herein lies the problem: I have a program that accepts complete commands from a file and executes them. It works perfectly. And now I'd just like to set an environment variable while each command runs... But alas no, the only way to do that is with runProcess, which expects me to parse the command line first. (Before anybody remarks that "words" will do this, consider the "echo" command, which treats whitespace meaningfully.) In the end I resorted to reading the source code for the module. After about 30 minutes of hacking, I got something which typechecks but throws a runtime exception. It appears that runCommand looks for binaries in the system search path, but the code I've concocted doesn't. (Despite being cut and pasted from the definition of runCommand.) The only thing I can think of is that the source code I'm looking at (GHC 6.8.3) is different from the version of the library I have (GHC 6.8.1). Anyway, the point I'm trying to get to is... would it be hard for however maintains this library to add a little more flexibility in what it can do please?

10 15

enumeration I/O and non-sequential access
by John Lato 02 Oct '08

02 Oct '08

Hello, I've recently been looking at Oleg's Iteratee approach to I/O (http://okmij.org/ftp/Haskell/Iteratee/) and I was wondering about something. In general this seems to be a very good approach to handling sequential access, but I don't see a means of applying it where non-sequential (esp. random) access is desired. In fact, the only way I see of doing so is to either hold references to all read data in memory until the file has finished processing, or to iterate over the file multiple times, depending on how the data is to be processed. I can't see how either of these approaches would scale well. Is this an actual problem? Is there already a solution that I'm not aware of? Thanks, John Lato

2 2

One liner?
by Paul Keir 02 Oct '08

02 Oct '08

Hi all, There's a common little situation I keep bumping up against. I don't understand where I'm going wrong, so I've made a little example. It's to do with binding a result to a variable name using "<-". This code works fine: ---------------------------------------------- module Main where import System.Directory (getDirectoryContents) main = do dc <- getDirectoryContents "./foo/" mapM_ putStrLn dc ---------------------------------------------- But if I try to avoid the use of the bind to "dc", I fail: ---------------------------------------------- mapM_ putStrLn (getDirectoryContents "./foo/") ---------------------------------------------- I've tried using map instead of mapM_, and inserted "return"s here and there, but no luck. Can anyone tell me where and why I'm going wrong? The error message is below. Cheers, Paul Couldn't match expected type `[String]' against inferred type `IO [FilePath]' In the second argument of `mapM_', namely `(getDirectoryContents "./foo/")' In the expression: mapM_ putStrLn (getDirectoryContents "./foo/") In the definition of `main': main = mapM_ putStrLn (getDirectoryContents "./foo/")

4 5

csv one-liner
by wman 02 Oct '08

02 Oct '08

I got asked how to do one particular thing in excel, which led to discssion with "our local MSOffice expert". During the discussion I stated that's it too much of a PITA and that I'd rather write a script. Long story short, I promised him a one-liner to "show the power and beauty of Haskell". I got the csv package from hackage, modified the parseCSVFromFile so it's returns IO CSV rather than IO (Either ParseError CSV), and finished with following code (writeFile "output.csv") =<< (liftM printCSV $ liftM (map updateLine) $ parseCSVFromFile "input.csv") Is there room for improvement ? Could it still be made into one-liner without modifying the csv module (and without resorting to case parseCSVFromFile "input.csv" of { Left _ -> []; Right x -> x} kind of tricks) ? Thanks, wman.

13 23

A question about constraints
by jean-christophe mincke 02 Oct '08

02 Oct '08

Hello, Given a type T, this type identifies a set of values and this set can be deduced from the structure of type T. i.e the type String is the set of all possible lists of character whatever their length. This being said, I have the following question: Given a type T, how is it possible to further restrict its set of values? i.e, in the above case, how is it possible to define a type String2 whose elements are any list of characters whose length is <= 5. I believe the best way to deal with that is to make String2 an ADT. This allows the constraint (in this case, the length) to be checked but hides the structure of the type, thus limits the use of pattern matching (in this case I do not want to hide the implementation of the type, so the ADT is not used that way). If one wants to use pattern matching, then the module must provide a way to convert from String2 to a type whose constructors are visible (asString in this exemple) module A ( String2 ,mkString2 ,asString ) where import List data String2 = String2 String mkString2 l = if (length l) <= 5 then String2 l else error "length > 5" asString (String2 l) = l Btw, F# has found a nice solution to this problem, it allows the user to define an "active pattern", that is, a pattern to applies on ADT: http://blogs.msdn.com/dsyme/archive/2007/04/07/draft-paper-on-f-active-patt… Is there another way to address that problem in Haskell? Thank you Regards J-C Mincke

4 3

[Streams] Couldn't match expected type ?`Distribution.Verbosity.Verbosity'
by Stephane Bortzmeyer 02 Oct '08

02 Oct '08

I cannot compile Streams 0.1: % darcs pull Pulling from "http://software.pupeno.com/Streams-0.1"... No remote changes to pull in! % make runhaskell Setup.lhs configure Setup.lhs:11:53: Couldn't match expected type `Distribution.Verbosity.Verbosity' against inferred type `IO FilePath' In the first argument of `readPackageDescription', namely `pkg_descr_file' In a 'do' expression: pkg_descr <- readPackageDescription pkg_descr_file In the expression: do pkg_descr_file <- defaultPackageDesc pkg_descr <- readPackageDescription pkg_descr_file let isWindows = "mingw" `isPrefixOf` System.Info.os config = ... defaultMainNoRead config make: *** [.setup-config] Error 1 % ghc --version The Glorious Glasgow Haskell Compilation System, version 6.8.2

2 4