March 2009 - Haskell-Cafe

Re: [Haskell] Lazy IO breaks purity
by Simon Marlow 06 Mar '09

06 Mar '09

Lennart Augustsson wrote: > I don't see any breaking of referential transparence in your code. > Every time you do an IO operation the result is basically > non-deterministic since you are talking to the outside world. > You're assuming the IO has some kind of semantics that Haskell makes > no promises about. > > I'm not saying that this isn't a problem, because it is. > But it doesn't break referential transparency, it just makes the > semantics of IO even more complicated. > > (I don't have a formal proof that unsafeInterleaveIO cannot break RT, > but I've not seen an example where it does yet.) So the argument is something like: we can think of the result of a call to unsafeInterleaveIO as having been chosen at the time we called unsafeInterleaveIO, rather than when its result is actually evaluated. This is on dodgy ground, IMO: either you admit that the IO monad contains an Oracle, or you admit it can time-travel. I don't believe in either of those things :-) Cheers, Simon > -- Lennart > > On Thu, Mar 5, 2009 at 2:12 AM, <oleg(a)okmij.org> wrote: >> >> We demonstrate how lazy IO breaks referential transparency. A pure >> function of the type Int->Int->Int gives different integers depending >> on the order of evaluation of its arguments. Our Haskell98 code uses >> nothing but the standard input. We conclude that extolling the purity >> of Haskell and advertising lazy IO is inconsistent. >> >> Henning Thielemann wrote on Haskell-Cafe: >>> Say I have a chain of functions: read a file, ... write that to a file, >>> all of these functions are written in a lazy way, which is currently >>> considered good style >> Lazy IO should not be considered good style. One of the common >> definitions of purity is that pure expressions should evaluate to the >> same results regardless of evaluation order, or that equals can be >> substituted for equals. If an expression of the type Int evaluates to >> 1, we should be able to replace every occurrence of the expression with >> 1 without changing the results and other observables. >> >> The expression (read s) where s is the result of the (hGetContents h1) >> action has the pure type, e.g., Int. Yet its evaluation does more than >> just producing an integer: it may also close a file associated with >> the handle h1. Closing the file has an observable effect: the file >> descriptor, which is a scarce resource, is freed. Some OS lock the >> open file, or prevent operations such as renaming and deletion on the >> open file. A file system whose file is open cannot be >> unmounted. Suppose I use an Haskell application such as an editor to >> process data from a removable drive. I mount the drive, tell the >> application the file name. The (still running) application finished >> with the file and displayed the result. And yet I can't unplug the >> removable drive, because it turns out that the final result was >> produced without needing to read all the data from the file, and the >> file remains unclosed. >> >> Some people say: the programmer should have used seq. That is the >> admission of guilt! An expression (read s)::Int that evaluates to 1 is >> equal to 1. So, one should be able substitute (read s) with 1. If the >> result of evaluating 1 turns out not needed for the final outcome, >> then not evaluating (read s) should not affect the outcome. And yet it >> does. One uses seq to force evaluation of an expression even if the >> result may be unused. Thus the expression of a pure type >> has *side-effect*. >> >> The advice about using seq reminds me of advice given to C programmers >> that they should not free a malloc'ed pointer twice, dereference a >> zero pointer and write past the boundary of an array. If lazy IO is >> considered good style given the proper use of seq, then C should be >> considered safe given the proper use of pointers and arrays. >> >> Side affects like closing a file are observable in the external >> world. A program may observe these effects, in an IO monad. One can >> argue there are no guarantees at all about what happens in the IO >> monad. Can side-effects of lazy IO be observable in _pure_ Haskell >> code, in functions with pure type? Yes, they can. The examples are >> depressingly easy to write, once one realizes that reading does have >> side effects, POSIX provides for file descriptor aliasing, and sharing >> becomes observable with side effects. Here is a simple Haskell98 code. >> >> >>> {- Haskell98! -} >>> >>> module Main where >>> >>> import System.IO >>> import System.Posix.IO (fdToHandle, stdInput) >>> >>> -- f1 and f2 are both pure functions, with the pure type. >>> -- Both compute the result of the subtraction e1 - e2. >>> -- The only difference between them is the sequence of >>> -- evaluating their arguments, e1 `seq` e2 vs. e2 `seq` e1 >>> -- For really pure functions, that difference should not be observable >>> >>> f1, f2:: Int -> Int -> Int >>> >>> f1 e1 e2 = e1 `seq` e2 `seq` e1 - e2 >>> f2 e1 e2 = e2 `seq` e1 `seq` e1 - e2 >>> >>> read_int s = read . head . words $ s >>> >>> main = do >>> let h1 = stdin >>> h2 <- fdToHandle stdInput >>> s1 <- hGetContents h1 >>> s2 <- hGetContents h2 >>> print $ f1 (read_int s1) (read_int s2) >>> -- print $ f2 (read_int s1) (read_int s2) >> >> One can compile it with GHC (I used 6.8.2, with and without -O2) and >> run like this >> ~> /tmp/a.out >> 1 >> 2 >> -1 >> That is, we run the program and type 1 and 2 as the inputs. The >> program prints out the result, -1. If we comment out the line >> "print $ f1 (read_int s1) (read_int s2)" and uncomment out the last >> line the transcript looks like this >> ~> /tmp/a.out >> 1 >> 2 >> 1 >> >> Running the code with Hugs exhibits the same behavior. Thus a pure >> function (-) of the pure type gives different results depending on the >> order of evaluating its arguments. >> >> Is 1 = -1? >> >> >> >> >> >> >> _______________________________________________ >> Haskell mailing list >> Haskell(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell >> > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell

6 5

Difficulties in accessing inner elements of data types
by David Miani 06 Mar '09

06 Mar '09

Hi, I'm working on a Haskell library for interacting with emacs org files. For those that do not know, an org file is a structured outline style file that has nested headings, text, tables and other elements. For example: * Heading 1 Some text, more text. This is a subelement of Heading 1 1. You can also have list 1. and nested lists 2. more... ** Nested Heading (subelement of Heading 1) text... (subelement of Nested Heading) ** Another level 2 heading (subelement of Heading 1) | Desc | Value | |-----------+--------------------------------------| | Table | You can also have tables in the file | | another | row | | seperator | you can have seps as well, eg | |-----------+--------------------------------------| * Another top level heading There are many more features, see orgmode.org My library enables read and write access to a subset of this format (eg lists aren't parsed atm). The data structures used for writing are: data OrgFile = OrgFile [OrgFileElement] data OrgFileElement = Table OrgTable | Paragraph String | Heading OrgHeading -- heading level, title, subelements data OrgHeading = OrgHeading Int String [OrgFileElement] data OrgTable = OrgTable [OrgTableRow] data OrgTableRow = OrgTableRow [String] | OrgTableRowSep To write a file you contruct a OrgFile out of those elements, and pass it to a writeOrgFile func. Eg: writeOrg $ OrgFile [Heading (OrgHeading 1 "h1" [Paragraph "str"])] would produce: * h1 str I was going to use the same data structures for reading an org file, but it quickly became apparent that this would not be suitable, as you needed the position of the file of an element to be able to report errors. Eg if you needed to report an error that a number was expected, the message "'cat' is not a number" is not very useful, but "Line 2031: 'cat' is not a number" is. So the data structures I used were: data FilePosition = FilePosition Line Column data WithPos a = WithPos { filePos :: FilePosition, innerValue :: a } data OrgTableP = OrgTableP [WithPos OrgTableRow] data OrgFileElementP = TableP OrgTableP | ParagraphP String | HeadingP OrgHeadingP data OrgHeadingP = OrgHeadingP Int String [WithPos OrgFileElementP] data OrgFileP = OrgFileP [WithPos OrgFileElementP] Finally there is a function readOrg, which takes a string, and returns an OrgTableP. Now, this all works as expected (files are correctly being parsed and written), however I am having a lot of trouble trying to come up with a decent API to work with this. While writing an OrgFile is fairly easy, reading (and accessing inner parts) of an org file is very tedious, and modifying them is horrendous. For example, to read the description line for the project named "Project14" in the file: * 2007 Projects ** Project 1 Description: 1 Tags: None ** Project 2 Tags: asdf,fdsa Description: hello * 2008 Projects * 2009 Projects ** Project14 Tags: RightProject Description: we want this requires the code: type ErrorS = String listToEither str [] = Left str listToEither _ (x:_) = Right x get14 :: OrgFileP -> Either ErrorS String get14 (OrgFileP elements) = getDesc =<< (getRightProject . concatProjects) elements where concatProjects :: [WithPos OrgFileElementP] -> [OrgHeadingP] concatProjects [] = [] concatProjects ((WithPos _ (HeadingP h)) : rest) = h : concatProjects rest concatProjects (_ : rest) = concatProjects rest getRightProject :: [OrgHeadingP] -> Either ErrorS OrgHeadingP getRightProject = listToEither "Couldn't find project14" . filter (\(OrgHeadingP _ name _) -> name == "Project14") getDesc :: OrgHeadingP -> Either ErrorS String getDesc (OrgHeadingP _ _ children) = case filter paragraphWithDesc (map innerValue children) of [] -> Left $ show (filePos $ head children) ++ ": Couldn't find desc in project" ((ParagraphP str):_) -> Right str _ -> error "should not be possible" paragraphWithDesc :: OrgFileElementP -> Bool paragraphWithDesc (ParagraphP str) = str =~ "Description" paragraphWithDesc _ = False If you think that is bad, try writing a function that adds the Tag "Hard" to Project2 :( What I really need is a DSL that would allow sql like queries on an OrgFileP. For example: select (anyHeading `next` headingWithName "Project14" `withFailMsg` "couldn't find p14" `next` paragraphMatchingRegex "Description" `withFailMsg` "no desc") org `output` paragraphText would return a String OR select (anyHeading `next` headingWithName "Project2" `next` paragraphMatchingRegex "Tag:") org `modify` paragraphText (++ ",Hard") would return an OrgFile, with the new Hard tag added. However, I don't know if this is even possible, how to do it, or if there is a better alternative to this. I would really apreciate any hints with regards to this. It would be useful to know if there are other libraries that also face this problem, and how they solved it. Finally, I would be grateful for any other advice regarding my code. One thing that has bugged me is my solution for having file position info - my solution never seemed very elegant. Thanks, David

5 5

Hint and Ambiguous Type issue
by Joseph Fredette 05 Mar '09

05 Mar '09

I've been working on a little project, and one of the things I need to do is dynamically compile and import a Haskell Source file containing filtering definitions. I've written a small monad called Filter which is simply: type Filter a = Reader (Config, Email) a To encompass all the email filtering. The method I need to import, filterMain, has type: filterMain :: Deliverable a => Filter a where Deliverable is a type class which abstracts over delivery to a path in the file system. The notion is that I can write a type like: data DEmail = {email :: Email, path :: FilePath} newtype Maildir = MD DEmail instance Deliverable Maildir where {- ... omitted -} However, Filter a should not be restricted to Deliverable types- it also encompasses the results of regular expression matching, etc, which are not -- in general -- Deliverable instances. My question is this, when importing the file containing the definitions of filterMain, I have the following code to grab filterMain and return it as a function. getFilterMain :: Deliverable a => FilePath -> Interpreter (Filter a) getFilterMain fMainLoc = do loadModules [fMainLoc]; setTopLevelModules [(takeWhile (/='.') fMainLoc)] fMain <- (interpret "(filterMain)" (as :: Deliverable a => Filter a)) return (fMain) However, when I try to compile this, I get the type error: Hackmain.hs:70:43: Ambiguous type variable `a' in the constraint: `Deliverable a' arising from a use of `getFilterMainStuff' at Hackmain.hs:70:43-60 Probable fix: add a type signature that fixes these type variable(s) My understanding is that a type like "Foo a => Bar a" (where Foo is a class and Bar is a datatype) would simply restrict the values of a to only those implementing Foo. But evidently I'm wrong. Is there a good (read, easy... :) ) fix to this? Any help would be greatly appreciated. /Joe PS. All the actual code is on patch-tag, here http://patch-tag.com/repo/Hackmail/home -- if anyone prefers to look at that directly, the relevant files are in Src, namely, Hackmain.hs, Filter.hs, and Deliverable.hs

4 7

Calculating with list comprehension
by R J 05 Mar '09

05 Mar '09

I can calculate non-nested list comprehensions without a problem, but am unable to calculate nested comprehensions involving, for example, the generation of a list of pairs where the first and separate elements are drawn from two separate lists, as in: [(a, b) | a <- [1..3], b <- [1..2]] How does one calculate the expansion of this list? The two rules for expanding list comprehensions are: 1. Generator rule: [e | x <- xs, Q] = concat (map f xs) where f x = [e | Q] 2. Guard rule: [e | p, Q] = if p then [e | Q] else [] There is a third rule that I've seen on the Internet, not in an authoritative text: [e | Q1 , Q2] = concat [ [e | Q 2] | Q1 ] I don't understand what this third rule means, or whether it's relevant. Concat and map are defined as: concat :: [[a]] -> [a] concat [] = [] concat (xs:xss) = xs ++ concat xss map :: (a -> b) -> [a] -> [b] map f [] = [] map f (x:xs) = f x : (map f xs) Any help is appreciated. _________________________________________________________________ Windows Live™: Life without walls. http://windowslive.com/explore?ocid=TXT_TAGLM_WL_allup_1a_explore_032009

2 1

Re: Left fold enumerator - a real pearl overlooked?
by John Lato 05 Mar '09

05 Mar '09

> John A. De Goes schrieb: > >> Elsewhere, laziness can be a real boon, so I don't understand your >> question, "Why have laziness in Haskell at all?" > > As I have written, many libaries process their data lazily (or could be > changed to do so without altering their interface) but their interface > can forbid application to data that is fetched from the outside world. > Say you are used to 'map', 'filter', 'foldr' - you cannot use them on > data fetched by the iteratee/enumerator approach. > Thank you for replying to this; it's good to see what features people would like to make iteratees more useful. Where did you get the idea that you can't use 'map'? IterateeGM is a Monad and Functor, so fmap is available for the resultant value. If you want to map over the elements of the stream, use the 'mapStream' function ('map_stream' in Oleg's writings). I never thought about writing a general iteratee fold because that's all iteratees are anyway; it's simple enough to make a foldl. It should be possible to write foldr for seekable resources by enumerating the stream backwards. That certainly wouldn't work for network I/O, unfortunately. Note that this is essentially the approach taken by lazy bytestrings, for example. There are other elements I'd want to address before adding this, however. There are also complications dealing with nested streams. I have some ideas, but the way forward is far from clear. filter should be fairly simple to implement with peek and drop. I'll look into it. Cheers, John

3 2

Theory about uncurried functions
by Peter Verswyvelen 05 Mar '09

05 Mar '09

Lambda calculus is a nice theory in which every function always has one input and one output. Functions with multiple arguments can be simulated because functions are first class and hence a function can "return" a function. Multiple outputs cannot be done, one must embed these outputs in some data type, e.g. using a tuple, or one must use continuation passing style. Now, does a similar theory exist of functions that always have one input and one output, but these inputs and outputs are *always* tuples? Or maybe this does not make any sense?

10 22

missing support to Data.Binary for uvector package
by Manlio Perillo 05 Mar '09

05 Mar '09

Hi. I'm still having problems with the uvector package. I have an IntMap (UArr xxx) data type, and I want to serialize it to disk, in binary format. I'm using the uvector package from http://patch-tag.com/repo/pumpkin-uvector/home The problem is with missing instance declarations, for Hyperstrict data type and Data.Array.Vector.UArr.UPrim. For the former, the instance is simple, but for the latter I have no idea about what to do. The full error message (GHC 6.8.2): No instance for (uvector-0.2:Data.Array.Vector.UArr.UPrim (Word32 uvector-0.2:Data.Array.Vector.Prim.Hyperstrict.:*: Word8)) arising from a use of `encode' at bin/process-data-1.hs:72:18-36 Possible fix: add an instance declaration for (uvector-0.2:Data.Array.Vector.UArr.UPrim (Word32 uvector-0.2:Data.Array.Vector.Prim.Hyperstrict.:*: Word8)) Thanks Manlio Perillo

3 2

monadic MapReduce
by Manlio Perillo 05 Mar '09

05 Mar '09

Hi. I have a function that do some IO (take a file path, read the file, parse, and return some data), and I would like to parallelize it, so that multiple files can be parsed in parallel. I would like to use the simple mapReduce function, from Real Word Haskell: mapReduce :: Strategy b -- evaluation strategy for mapping -> (a -> b) -- map function -> Strategy c -- evaluation strategy for reduction -> ([b] -> c) -- reduce function -> [a] -- list to map over -> c mapReduce mapStrat mapFunc reduceStrat reduceFunc input = mapResult `pseq` reduceResult where mapResult = parMap mapStrat mapFunc input reduceResult = reduceFunc mapResult `using` reduceStrat Is this possible? Thanks Manlio Perillo I

4 7

Re: [Haskell-cafe] Re: [Haskell] Lazy IO breaks purity
by Svein Ove Aas 05 Mar '09

05 Mar '09

On Thu, Mar 5, 2009 at 2:08 PM, Simon Marlow <marlowsd(a)gmail.com> wrote: > > So the argument is something like: we can think of the result of a call to > unsafeInterleaveIO as having been chosen at the time we called > unsafeInterleaveIO, rather than when its result is actually evaluated. This > is on dodgy ground, IMO: either you admit that the IO monad contains an > Oracle, or you admit it can time-travel. I don't believe in either of > those things :-) > As it turns out, time-travel as a vehicle for computation has a long tradition in the more advanced systems; see http://www.frc.ri.cmu.edu/~hpm/project.archive/general.articles/1991/TempCo… for an example.

1 0

Finding the Convex Hull (Problem 12 of Real World Haskell)
by Rob Crowther 05 Mar '09

05 Mar '09

I wrote a "solution" to this problem, but it appears to return incorrect results. There's a pastebin of the code at http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2121 and a picture of the inputs, outputs, and expected results graphed at http://img510.imageshack.us/img510/9971/resultsg.jpg I'm wondering if this is a flaw in my code, my understanding of the problem, or both. Any ideas on how to track this one down would be very much appreciated. Thank you! -- ヽ(^o^)ノ -rob

3 2