- Haskell-Cafe - Haskell.org

Newbie: Is‘type’ synonym hiding two much?
by Dmitri O.Kondratiev 22 Mar '07

22 Mar '07

I am learning Haskell working through Simon Thompson book "Haskell The Craft of Functional Programming" (second edition). Solving problems in the book with more or less success I arrived almost to the end of the book at the section 17.5 "Case study: parsing expressions". Most probably the question I am going to ask here is very stupid, so please bear with me. In any case, after going so far in the book I felt certain that I know what function declaration means. So I thought that declaration: F :: a -> b -> c Is the same as: F :: a -> (b -> c) And means either: - a function 'f' of one argument of type 'a' that returns a function of type (b -> c), or it can also be interpreted as: - a function 'f' of two arguments of type 'a' and 'b' returning value of type 'c' Now, in the 17.5 section of a book one may see the following declarations: succeed :: b -> Parse a b *Before looking at 'succeed' function definition* one may think that 'succeed' is a function of *one* argument of type 'b' that returns object of type 'Parse a b'. Yet, function definition given in the book is: succeed val inp = [(val, inp)] Looking at this definition, I am inclined to think that 'succeed' is a function of *two* arguments named 'val' and 'inp' in the definition ! How can such a definition be correct? Ok, lets see what is this 'Parse a b' type is: type Parse a b = [a] -> [(b, [a])] So how does this help to make definition 'succeed val inp = [(val, inp)]' sound right? Well, the only way for me to make sense out of this is as follows. In this case Haskell 'type' makes type synonym for the type: [a] -> [(b, [a])] In order not to get out of my mind I start thinking about 'type' as a macro substitution mechanism. Then I do this substitution *myself as a Haskell runtime* and get in the result the following declaration of a * real function that Haskell runtime* works with: Succeed :: b -> [a] -> [(b, [a])] Great! This last declaration matches perfectly with function definition: succeed val inp = [(val, inp)] So I start feeling better, after all, it looks like my understanding of Haskell function declarations is not flawed too much. Well, but here comes my main questions! So: 1. Should I work every time as a macro translator when I just see *!any!* function declaration? 2. Should I search through main and imported modules for treacherous 'type' constructs? 3. Where, in this case goes implementation abstraction principle? Why I must provide *all* the details about function argument type structure in order to understand how this function works? Another example of a similar function from the book is: alt :: Parse a b -> Parse a b -> Parse a b alt p1 p2 inp = p1 inp ++ p2 inp In function definition I see three parameters: p1 – matches with function declaration perfectly p2 – matches with function declaration perfectly inp – how to match this parameter with function declaration ? I can match 'inp' parameter with 'alt' function declaration *only* after working as macro processor that expands type synonym 'Parse a b' into '[a] -> [(b, [a])]' and getting *real* declaration: alt :: [a] -> [(b, [a])] -> [a] -> [(b, [a])] -> [a] -> [(b, [a])] with that matches alt p1 p2 inp = p1 inp ++ p2 inp where 'inp' matches with *last* '[a]' argument. It seems that life of "human macro processor" becomes really hard when not trivial functions with 'type' synonym arguments come into play! Where I am wrong? Please enlighten me; I am really at a loss! And thanks for reading all this! Below I give a code example of these functions. Thanks, Dima module Parser where import Data.Char type Parse a b = [a] -> [(b, [a])] none :: Parse a b none inp = [] succeed :: b -> Parse a b succeed val inp = [(val, inp)] suc:: b -> [a] -> [(b, [a])] suc val inp = [(val, inp)] spot :: (a -> Bool) -> Parse a a spot p [] = [] spot p (x:xs) | p x = [(x, xs)] | otherwise = [] alt :: Parse a b -> Parse a b -> Parse a b alt p1 p2 inp = p1 inp ++ p2 inp bracket = spot (=='(') dig = spot isDigit t1 = (bracket `alt` dig) "234"

4 3

Re: [Hs-Generics] FW: [Haskell-cafe] SYB vs HList (again)
by oleg＠pobox.com 22 Mar '07

22 Mar '07

[Please follow-up to generics(a)haskell.org] S. Alexander Jacobson wrote: > HLists require you to define Labels and basically only use label > values that are themselves either scalar or HLists. > ... > With SYB you create field labels using newtype (or data) declarations > e.g. > > data Salary = S {salary::Float} > > With HList, label declarations are really verbose e.g. > > data SalaryLabel deriving(Typeable) > type Salary = Field (Proxy SalaryLabel) Int > salary = proxy :: Proxy FooLabel Actually there is no requirement that HList record names must be scalar `labels', must be Proxies and require such a complex declaration. From HList's high point of view, any collection can be a record provided the type of each item is unique and there is some way to extract the value associated with that type. The HList library provides two implementations of Records (and there was one more, obsolete now). There could be more. For example, I have just committed a yet another implementation, http://darcs.haskell.org/HList/src/RecordD.hs Here a record is a list of things that have a type and a value and provide a way to extract that value. The example from the end of this file seems worth quoting: > data Name = Name String String deriving Show > newtype Salary = S Float deriving Show > data Dept = D String Int deriving Show > > person = (Name "Joe" "Doe") .*. (S 1000) .*. (D "CIO" 123) .*. emptyRecord > > -- could be derived automatically, like Typeable... > instance Fieldish Name (String,String) where > fromField (Name s1 s2) = (s1,s2) > instance Fieldish Salary Float where > fromField (S n) = n > instance Fieldish Dept (String,Int) where > fromField (D s n) = (s,n) > > test1 = show person > -- When a field acts as a label, only its type matters, not the contents > test2 = person .!. (Name undefined undefined) > test3 = person .!. (undefined::Salary) > test5 = person .!. (D "xxx" 111) > I don't know exactly how HList handles default values but I assume you > can restrict use of those values to explicit deserialization contexts. > Is that correct? I'm not sure what you mean about the restriction of default values to deserialization contexts. Anyway, HList provides a left-biased union of two records: hLeftUnion r1 r2 is the record r1 augmented with all the fields from r2 that didn't occur in r2. One may consider r2 to be the record with default fields and the corresponding values. > It would be really nice if there was some way to tell Haskell that > HLists have no more fields than the ones you happen to be getting and > setting in your code. Effectively that would mean you get data > structure inference not just function type inference which would be > really cool! I'm not sure I follow. Could you outline an example of the code you wish work? Incidentally, a lot of the library depends on the record types being members of some specific classes. One can define > newtype ClosedRecord = ClosedRecord r To make a ClosedRecord to be a record from which we can extract the values of some fields, we merely need to say > instance HasField l r v => HasField l (ClosedRecord r) v > where hLookupByLabel l (ClosedRecord r) v = hLookupByLabel l r v Since we did not make this record the member of HExtend or HAppend, it is not extensible.

3 3

How do I do conditional tail recursion in a monad?
by DavidA 22 Mar '07

22 Mar '07

Hi, I would like to write a function untilM, which would be to until as mapM is to map. An example use would be if I had a function dice :: State Int Int which returns random dice throws within a state monad. Then I'd like to be able to do something like untilM (\(s,p)-> s>=100) f (0,1) where f (s,p) = do d <- dice return (s+d, p*d) This should throw dice until the sum exceeds 100, and keeping track of the product as we go along. The problem is that I get stuck trying to manage the interaction of the conditional and the recursion in untilM. Let's start with until: until p f x = if p x then x else until p f (f x) So I figure untilM should look something like: untilM :: Monad m => (a -> Bool) -> (a -> m a) -> a -> m a untilM p f x = return (if p x then x else untilM p f (f x)) The problem is that the two branches of the conditional have different types. If I try to remedy that by changing "then x" to "then return x", it still isn't happy. (My real question is, how do I do conditional tail recursion in a monad?) Thanks in advance.

6 9

Newbie vs. laziness
by Alex Queiroz 21 Mar '07

21 Mar '07

Hallo list, I don't quite get how ($!) works. I have this function: dbCreateIndices con dtn dof = do let dummy = newDbItem let query = "SELECT id FROM " ++ (dtn dummy) ++ " ORDER BY " ++ (dof dummy) ids <- liftM (map fromSql . concat ) $! quickQuery con query [] return $ IntMap.fromList $ zip ids [0..] quickQuery returns a lazy list of results, and I expected ($!) to make it strict. But my program crashes if I use it this way. But, if I add a print to the function: dbCreateIndices con dtn dof = do let dummy = newDbItem let query = "SELECT id FROM " ++ (dtn dummy) ++ " ORDER BY " ++ (dof dummy) ids <- liftM (map fromSql . concat ) $! quickQuery con query [] print ids return $ IntMap.fromList $ zip ids [0..] print makes the ids list strict and all is well. How is the correct way to use ($!) ? Cheers, -- -alex http://www.ventonegro.org/

4 6

Re: [Haskell-cafe] Lazy IO and closing of file handles
by Bertram Felgenhauer 21 Mar '07

21 Mar '07

Ketil Malde wrote: > Bertram Felgenhauer wrote: > >>> type Subject = String > >>> data Email = Email {from :: From, subject :: Subject} deriving Show > >data Email = Email {from :: !From, subject :: !Subject} deriving Show > ...except that From and Subject are Strings, and thus the strictness > annotation only forces WHNF. I.e., you also need to modify parseEmail > to force these. > > -k You're right. Actually, the program will be strict enough if the From header always precedes the Subject header (which was the case in my tests), but that's not immediately obvious. Modifying getHeader to force its result is the clean solution, say: getHeader = forceString . fromMaybe "N/A" . flip lookup headers forceString s = length s `seq` s Having to rely on GC to close the fds quickly enough is another problem; can this be solved on the library side, maybe by performing GCs when running out of FDs? Bertram

3 3

Is ([] -> []) an arrow?
by Chad Scherrer 21 Mar '07

21 Mar '07

In John Hughes's "Programming With Arrows" (http://www.cs.chalmers.se/~rjmh/afp-arrows.pdf) he discusses a "stream function" type newtype SF a b = SF {runSF :: [a] -> [b]} and gives instance Arrow SF where .... He gives some examples using this, and everything seems to go just fine. But in Ross Patterson's "Arrows and Computation" (http://www.soi.city.ac.uk/~ross/papers/fop.html) he says that newtype ListMap i o = LM ([i] -> [o]) is ALMOST an arrow. Now, I've heard (but never verified) that IO fails to satisfy some monad laws, yet here we are, using it as a monad. Is a similar kind of thing going on here? Has anyone hit any snags in using this instance? Thanks, Chad

2 1

Partial Evaluation
by jim burton 21 Mar '07

21 Mar '07

I am reading Hudak's paper Modular Domain Specific Languages and Tools [1] and am confused by his use of the term `Partial Evaluation'. I understand it to mean supplying some but not all arguments to a function, e.g. (+3) but it seems to mean something else too. This is in the context of optimising performance: "We have used existing partial evaluation techniques to do this...Unfortunately, there does not currently exist a suitable, easy-to-use partial evaluator for Haskell. Our approach was to convert the Haskell program to Scheme, partially evaluate the Scheme program, and then translate back into Haskell." What does P.E, mean here? Thanks, [1] Available http://wiki.ittc.ku.edu/lambda/Image:Hudak-Modular_Domain_Specific_Language…

4 3

There can be only one fix? Pondering Bekic's lemma
by Nicolas Frisby 21 Mar '07

21 Mar '07

Bekic's lemma [1], allows us to transform nested fixed points into a single fixed point, such as: fix (\x -> fix (\y -> f (x, y))) = fix f where f :: (a, a) -> a This depends on having "true products," though I'm not exactly sure what that means. Mutual recursion can also be described with recursion and products f = \a -> ... g a ... g = \b -> ... f b ... can be defined as (f, g) = fix (\knot -> \a -> ... (snd knot) a ..., \b -> ... (fst knot) b ...) My question is: Given products and a fixed point combinator, can any pure expression be transformed into a corresponding expression that has just a single use of fix? If yes, has there been any usage of such a transformation, or is it just crazy? If no, could you provide a counter-example? Thanks for playing along, Nick [1] - Bekic has an entire book, but the most available reference for this I found is Levent Erkök's thesis regarding MonadFix/mfix (pgs 16 and 141). [Also, I cannot figure out how to get the proper symbol above that c in Bekic... sorry about that. I'd appreciate if someone told me how; does Unicode even have it?]

5 6

Design and state...
by Magnus Therning 21 Mar '07

21 Mar '07

Recently I've been hacking together a small Haskell module on top of ptrace(2). It's comming along nicely, but it's very low level. The signals arrive in a list: wait :: Int -> IO [Signal] and processing of the signals can be done using e.g. mapM_: wait childPid >>= mapM_ processSignal In a few cases this low level requires quite a bit of extra code. Code needs to be repeated in every program using the module. Dealing with breakpoints is a good example: - Setting a breakpoint requires storing the old instruction at the address - When hitting a breakpoint the old instruction should be put back, EIP backed up, perform one single-step, and last put the breakpoint back again. I believe adding another layer on top of what I have now seems like a good idea. AFAICS that means having a state (I must keep track of the original instruction). That can easily be done by wrapping IO in a StateT: forEachSignal:: Int -> (Signal -> IO ()) -> StateT DbgEnv IO () forEachSignal childPid procSignal = ... (Or would it be better using IORefs and "OO" in the way described in "IO Inside"[1]?) What I am struggling with is how to allow the user of the module to have state as well. I can see how "OO"[1] can be used to solve it, but is there a more elegant, maybe more idiomatic (Haskellic??), way? Or am I missing a more elegant way of dealing with this? /M [1]: http://haskell.org/haskellwiki/IO_inside#Example:_emulating_OOP_with_record… -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus(a)therning.org Jabber: magnus.therning(a)gmail.com http://therning.org/magnus

2 2

Lazy IO and closing of file handles
by Pete Kazmier 21 Mar '07

21 Mar '07

When using readFile to process a large number of files, I am exceeding the resource limits for the maximum number of open file descriptors on my system. How can I enhance my program to deal with this situation without making significant changes? My program takes one or more directories that contain email messages, stored one per file, and prints a list of all the email threads. Here is a snippet of output: New addition to the Kazmier family Casey Kazmier Memoization in Erlang? Thomas Johnsson Ulf Wiger $AL/EAB$ As a newcomer to Haskell, I am intrigued by lazy evaluation and how it can influence one's designs. With that said, I wrote the program as a sequence of list manipulations which seemed quite natural to do in Haskell starting with reading the contents of the each file. Here is the algorithm at the high level: 1. Read contents of all files returning a list of Strings 2. Map over the list and parse each String as an Email 3. Sort the list of Emails 4. Group the list of Emails by Subject 5. Map over the grouped list to create a list of Threads 6. Finally, print the list of Threads It is my understanding that, as a result of lazy IO, the entire file does not need to be read into memory because parseEmail only inspects the topmost portion of the email (its headers), which is a key part of my design as some of the files can be quite large. Unfortunately, as soon as I run this program on a directory with more than 1024 files, GHC craps out on me due to resource limits. It seems that the handles opened by readFile remain open. Would this be common across all Haskell implementations? How do I go about fixing this without making a significant number of changes to my program? Did I make a mistake in steps 1 and 2 above? Should I have read and parsed a single file at a time, and then move on to the next? I'd appreciate any other comments on the program as well. I feel this is the best example of Haskell code that I have written. Compared to the first version of this program I wrote a few months ago, this is a hundred times better. Here is the program: > module Main where > > import Control.Monad (filterM, liftM) > import Data.List > import Data.Maybe > import System.Directory > import System.Environment > > type From = String > type Subject = String > data Email = Email {from :: From, subject :: Subject} deriving Show > data Thread = Thread [Email] > > instance Show Thread where > show (Thread emails@(e:es)) = title ++ senders > where > title = newline . bolder . subject $ e > sender = newline . indent . from > senders = concatMap sender emails > newline = (++ "\n") > indent = (" " ++) > bolder = ("\27[0;32;40m" ++) . (++ "\27[0m") > > main = > getArgs >>= > mapM fileContentsOfDirectory >>= > mapM_ print . threadEmails . map parseEmail . concat > > fileContentsOfDirectory :: FilePath -> IO [String] > fileContentsOfDirectory dir = > setCurrentDirectory dir >> > getDirectoryContents dir >>= > filterM doesFileExist >>= -- ignore directories > mapM readFile > > parseEmail :: String -> Email > parseEmail text = > Email (getHeader "From") (getHeader "Subject") > where > getHeader = fromMaybe "N/A" . flip lookup headers > headers = concatMap mkassoc . takeWhile (/="") $ lines text > mkassoc s = case findIndex (==':') s of > Just n -> [(take n s, drop (n+2) s)] > Nothing -> [] > > threadEmails :: [Email] -> [Thread] > threadEmails = > map Thread . groupBy (fuzzy (==)) . sortBy (fuzzy compare) > where > fuzzy fn e e' = stripReFwd (subject e) `fn` stripReFwd (subject e') > stripReFwd = stripSpaces . reverse . stripToColon . reverse > stripSpaces = dropWhile (==' ') > stripToColon = takeWhile (/=':')

22 44