- Haskell-Cafe - Haskell.org

Prettyprinting infix expressions with HughesPJ
by Alfonso Acosta 11 Apr '07

11 Apr '07

Hi all, I have to prettyprint infix expressions writing the least possible parenthesis (taking in account precedence and associativity). A simplified expression type could be: data Expr = Val String | -- Binary operators (using infix constructors) Expr :+: Expr | Expr :-: Expr | Expr :*: Expr | Expr :/: Expr | Expr :^: Expr | -- Unary operators Negate Expr I'm using HughesPJ for the rest of my AST (not just expressions) but the library doesn't provide any mechanism to help coding this kind of prettyprinter so I decided to simply use the standard showsPrec and then feed HughesPJ with the obtained text . showsPrec helps to take advantage of the precedence information. However, I don't find a way to remove parenthesis according to associativity. I'm sure this kind of prettyprinting has been already done zillions of times in Haskell. Any suggestions? Thanks in advance, Alfonso Acosta

2 3

Type checking and locating token with Parsec
by Joel Reymont 10 Apr '07

10 Apr '07

Folks, Imagine a language where Num + Num yields a Num and Str + Num yields a Str but Num + Str should not be allowed. I implemented parsing for such a language in OCaml with a yacc-based parser without an additional type-checking pass, entirely within the yacc grammar. I tried to take such an approach with Parsec but hit the roadblock with buildExpressionParser since it returns the same type as the token parser given to it. Rather than have numerical expressions, string expressions, etc., as separate types, I simplified things down to a single expression type that holds my booleans, strings and numbers. I now need to implement type checking of my parsed AST. The main issue is error reporting. I'm not sure where to get token location with Parsec and how to elegantly embed it in my AST. Has anyone implemented type checking on top of a Parsec-based parser? How did you locate your tokens? Thanks, Joel -- http://wagerlabs.com/

2 1

Re: [Haskell-cafe] Weaving fun
by Dave Feustel 10 Apr '07

10 Apr '07

I ask this question because I want to program a recently published algorithm for directly enumerating all prime numbers. The algorithm description uses infinite sets. The algorithm could possibly be programmed using lazy evaluation. -----Original Message----- >From: Ricardo Herrmann <rherrmann(a)gmail.com> >Sent: Apr 10, 2007 7:24 PM >To: Haskell-Cafe(a)haskell.org >Subject: Re: [Haskell-cafe] Weaving fun > >This reminded me of "interleaving" as in: > >Backtracking, Interleaving, and Terminating Monad Transformers >http://www.cs.rutgers.edu/~ccshan/logicprog/LogicT-icfp2005.pdf > >On 4/10/07, Dave Feustel <dfeustel(a)mindspring.com> wrote: >> >> Talk about synchronicity! I was just wondering whether 'weaving' of >> infinite lists is possible. >> >> eg weave the infinite lists [2,4..], [3,6..], [5,10..] >> to get [2,3,4,5,6,8,9,10,..] >> >> Is this kind of lazy evaluation possible? >> >> Thanks, >> Dave Feustel http://RepublicBroadcasting.org - Because You CAN Handle The Truth! http://iceagenow.com - Because Global Warming Is A Scam!

1 0

operating on a hundred files at once
by Jefferson Heard 10 Apr '07

10 Apr '07

I have a series of NxM numeric tables I'm doing a quick mean/variance/t-test etcetera on. The cell t1 [i,j] corresponds exactly to the cells t2..N [i,j], and so it's perfectly possible to read one item at a time from each of the 100 files and compute the mean/variance etcetera on all cells that way. So what I propose to do is something along the lines of: openAndProcess filename = f <- readFile filename return (map (L.split ',') . lines $ f) main = do fs <- getArgs let items = map (map read) . map openAndProcess fs in do print . map (map $ mean) items print . map (map $ variance) items How close am I to doing the right thing here? As I understand it, this will result in one hundred IO [String] instances being returned by the call to (map openAndProcess $ filenames). Do I need to do something special to lift (read), (mean), and (variance), or even (map) into the IO monad so they can process the input as needed? Thanks in advance, -- Jeff

5 8

Checking for correct invocation of a command line / shell haskell program
by Thomas Hartman 10 Apr '07

10 Apr '07

New wiki page: Checking for correct invocation of a command line haskell program at http://haskell.org/haskellwiki/Checking_for_correct_invocation_of_a_command… This is a simple cookbook / boilerplate example I thought should go in a haskell wiki somewhere. I linked it from http://haskell.org/haskellwiki/Simple_unix_tools Perhaps it could be linked from other places as well. Hope this helps!

1 1

Type level programming to eliminate array bound checking, a real world use
by Vivian McPhail 10 Apr '07

10 Apr '07

Hi All,Inspired by Oleg's "Eliminating Array Bound Checking through Non-dependent types" http://okmij.org/ftp/Haskell/types.html#branding,I am attempting to write code that will receive an array from C land and convert it to a type safe representation. The array could have n dimensions where n > 2. I receive the number of dimensions as a list of Ints [Int]. To do type-safe programming I need to convert this to a type level representation. Using CPS (thanks to ski on #haskell) I can convert an Int to the type level. But I have found it impossible to insert this type-level Digits representation into an HList. In Oleg's examples with vectors he types in by hand the data whose type represents the size of the vector: sample_v = listVec (D2 Sz) [True,False] where (D2 Sz) is the size of the vector and the type is: ArbPrecDecT> :t sample_v Vec (D2 Sz) Bool In a real program we can't expect the programmer to type in the size of the data, it needs to be done programmatically, and this is where I am stuck. Could someone please point me in the right direction, or explain why what I'm trying to do won't work? Basically I'm looking for a function int2typelevel :: (HList l) :: [Int] -> l I thought that this would work because HLists can have elements of different types and I can already (modulo CPS) convert an Int to it's Digits type level representation. One approach which won't work is existentially wrapping the result of num2digits in a GADT, because this hides the type from the type-checker and then can't be used for bounds checking. Here is an example of what I want to be able to do: add :: Equal size1 size2 => Array size1 idx -> Array size2 idx -> Array size1 idx for example: data Array size idx = Array size (MArray idx Double) add (Array (DCons (D1 (D2 Sz)) (DCons (D3 Sz) DNil)) (12,3)) (Array (DCons (D1 (D2 Sz)) (DCons (D3 Sz) DNil)) (12,3)) the sizes are statically checked and I don't have to do runtime checking on the idx. This message is a literate source file. The commented out function at the end illustrates the problem. Thanks, Vivian >{-# OPTIONS -fglasgow-exts #-} > >-- copied from http://okmij.org/ftp/Haskell/number-parameterized-types.html > >module Digits where > >data D0 a = D0 a deriving(Eq,Read,Show) >data D1 a = D1 a deriving(Eq,Read,Show) >data D2 a = D2 a deriving(Eq,Read,Show) >data D3 a = D3 a deriving(Eq,Read,Show) >data D4 a = D4 a deriving(Eq,Read,Show) >data D5 a = D5 a deriving(Eq,Read,Show) >data D6 a = D6 a deriving(Eq,Read,Show) >data D7 a = D7 a deriving(Eq,Read,Show) >data D8 a = D8 a deriving(Eq,Read,Show) >data D9 a = D9 a deriving(Eq,Read,Show) > >class Digits ds where -- class of digit sequences > ds2num:: (Num a) => ds -> a -> a -- CPS style > >data Sz = Sz -- zero size (or the Nil of the sequence) > deriving(Eq,Read,Show) > >instance Digits Sz where > ds2num _ acc = acc > >instance (Digits ds) => Digits (D0 ds) where > ds2num dds acc = ds2num (t22 dds) (10*acc) >instance (Digits ds) => Digits (D1 ds) where > ds2num dds acc = ds2num (t22 dds) (10*acc + 1) >instance (Digits ds) => Digits (D2 ds) where > ds2num dds acc = ds2num (t22 dds) (10*acc + 2) >instance (Digits ds) => Digits (D3 ds) where > ds2num dds acc = ds2num (t22 dds) (10*acc + 3) >instance (Digits ds) => Digits (D4 ds) where > ds2num dds acc = ds2num (t22 dds) (10*acc + 4) >instance (Digits ds) => Digits (D5 ds) where > ds2num dds acc = ds2num (t22 dds) (10*acc + 5) >instance (Digits ds) => Digits (D6 ds) where > ds2num dds acc = ds2num (t22 dds) (10*acc + 6) >instance (Digits ds) => Digits (D7 ds) where > ds2num dds acc = ds2num (t22 dds) (10*acc + 7) >instance (Digits ds) => Digits (D8 ds) where > ds2num dds acc = ds2num (t22 dds) (10*acc + 8) >instance (Digits ds) => Digits (D9 ds) where > ds2num dds acc = ds2num (t22 dds) (10*acc + 9) > >t22::(f x) -> x; t22 = undefined > >-- Class of non-negative numbers >-- This is a restriction on Digits. It is not possible to make >-- such a restriction in SML. >class {- (Digits c) => -} Card c where > c2num:: (Num a) => c -> a > >instance Card Sz where c2num c = ds2num c 0 >--instance (NonZeroDigit d,Digits (d ds)) => Card (Sz (d ds)) where >instance (Digits ds) => Card (D1 ds) where c2num c = ds2num c 0 >instance (Digits ds) => Card (D2 ds) where c2num c = ds2num c 0 >instance (Digits ds) => Card (D3 ds) where c2num c = ds2num c 0 >instance (Digits ds) => Card (D4 ds) where c2num c = ds2num c 0 >instance (Digits ds) => Card (D5 ds) where c2num c = ds2num c 0 >instance (Digits ds) => Card (D6 ds) where c2num c = ds2num c 0 >instance (Digits ds) => Card (D7 ds) where c2num c = ds2num c 0 >instance (Digits ds) => Card (D8 ds) where c2num c = ds2num c 0 >instance (Digits ds) => Card (D9 ds) where c2num c = ds2num c 0 > >-- Support for "generic" cards >-- We introduce a data constructor CardC_unused merely for the sake of >-- Haskell98. With the GHC extension, we can simply omit the data >-- constructor and keep the type CardC purely abstract and phantom. >data CardC c1 c2 = CardC_unused > >cardc:: (Card c1, Card c2) => c1 -> c2 -> CardC c1 c2 >cardc = undefined >cardc1::CardC c1 c2 -> c1; cardc1 = undefined >cardc2::CardC c1 c2 -> c2; cardc2 = undefined > >instance (Card c1, Card c2) => Card (CardC c1 c2) where > c2num c12 = c2num (cardc1 c12) + c2num (cardc2 c12) > >----------------------------------------------------------------------------- >-- make lists > >-- copied from HList: http://okmij.org/ftp/Haskell/types.html#HList > >data DNil = DNil deriving (Eq,Show,Read) >data DCons e l = DCons e l deriving (Eq,Show,Read) > >class DList l >instance DList DNil >instance (Digits e, DList l) => DList (DCons e l) > >dNil :: DNil >dNil = DNil > >dCons :: forall e. Digits e => (DList l => e -> l -> DCons e l) >dCons e l = DCons e l > >-- ^ Oleg >----------------------------------------------------------------------------- >-- v Vivian > >-- CPS >num2digits :: (Integral a, Show a) => a -> (forall ds. (Digits ds) => ds -> o) -> o >num2digits n = str2digits (show n) > >str2digits :: String -> (forall ds. (Digits ds) => ds -> o) -> o >str2digits [] k = k Sz >str2digits ('0' : ss) k = str2digits ss (\ds -> k (D0 ds)) >str2digits ('1' : ss) k = str2digits ss (\ds -> k (D1 ds)) >str2digits ('2' : ss) k = str2digits ss (\ds -> k (D2 ds)) >str2digits ('3' : ss) k = str2digits ss (\ds -> k (D3 ds)) >str2digits ('4' : ss) k = str2digits ss (\ds -> k (D4 ds)) >str2digits ('5' : ss) k = str2digits ss (\ds -> k (D5 ds)) >str2digits ('6' : ss) k = str2digits ss (\ds -> k (D6 ds)) >str2digits ('7' : ss) k = str2digits ss (\ds -> k (D7 ds)) >str2digits ('8' : ss) k = str2digits ss (\ds -> k (D8 ds)) >str2digits ('9' : ss) k = str2digits ss (\ds -> k (D9 ds)) > >----------------------------------------------------------------------------- > >--test = num2str 10 (\x -> dCons x dNil)

1 0

Profiling makes memory leak go away? Is Haskell a practical language?
by Oren Ben-Kiki 10 Apr '07

10 Apr '07

Chasing down my memory leak I got into a weird situation where adding a magic manual SCC section and compiling with -prof makes the leak disappear. Now, I'll take any solution I can find - but this black voodoo only works for the short program I created for investigating the leak. It fails on the real program. Probably not enough fingernails in the voodoo doll or something :-( The code is in http://hpaste.org/1314#a1 if anyone at all is willing to take pity on me and explain what I'm doing wrong. This is the second system I tried writing in Haskell, and in both cases I hit a brick wall due to uncontrollable memory consumption. I'm just about ready to give up on Haskell as a practical language for non-trivial tasks. I can achieve the results I want in very short, elegant code... and as such it will have a place in my toolbox for various small tasks... but I lack the deep lore required to make it behave well for "large" inputs. At this point I have to take it on faith that it is even possible to do so in the first place :-(

2 1

Parsec: Help needed with simple parser
by Joel Reymont 10 Apr '07

10 Apr '07

Folks, I wrote a parser for what should be a simple expression but it's not working. Any help is appreciated! My expression is x + 1 where x can be either "Close", or "Close[N]" or "Close[N] of DataM where N and M are positive integers. What happens in my case is that 1 + x parses fine but x + 1 doesn't. In fact, I would be fine with parsing Close + such that it ignores the plus and returns the parse. Thanks, Joel -- http://wagerlabs.com/

2 2

Re: [Haskell-cafe] operating on a hundred files at once
by Chad Scherrer 10 Apr '07

10 Apr '07

Hi Jeff, > I have a series of NxM numeric tables I'm doing a quick > mean/variance/t-test etcetera on. The cell t1 [i,j] corresponds exactly > to the cells t2..N [i,j], and so it's perfectly possible to read one > item at a time from each of the 100 files and compute the mean/variance > etcetera on all cells that way. So after mapping openAndProcess, you have a 100xNxM "array" (really a list-of-lists-of-lists), right? And then when you take means and variances, which index are you doing this with respect to? As I read it, you seem to be trying to eliminate the first axis, and end up with an NxM "array". If this is the case, let's say we have mean, variance :: [Double] -> Double openAndProcess :: String -> IO (Matrix String) Here, defining type Matrix a = [[a]] makes it easier to keep the types straight. Then you have these building blocks: (map . map . map) read :: [Matrix String] -> [Matrix Double] transpose2 :: [Matrix Double] -> Matrix [Double] (a couple of lines, maybe even a one-liner, if you use that [a] is a monad) (map . map) mean :: Matrix [Double] -> Matrix Double Composing these gives a function [Matrix String] -> Matrix Double, so once we get to [Matrix String], we're effectively done. you also use map OpenAndProcess :: [String] -> [IO (Matrix String)] You can use sequence to get the IO outside the list, so now you have IO [Matrix String]. All you have to do now is use liftM on your function [Matrix String] -> Matrix Double, which turns it into a function IO [Matrix String] -> IO (Matrix Double). -- Chad Scherrer "Time flies like an arrow; fruit flies like a banana" -- Groucho Marx

1 0

Parsec: buildExpressionParser of a different type than parsed term
by Joel Reymont 10 Apr '07

10 Apr '07

Folks, I'm trying to parse NumExpr > NumExpr (example) which should return a logical expression while parsing numeric terms. I can't figure out how to make buildExpressionParser do this for me since it takes the type of the term parser given to it. If I supply a parser for numeric terms then I cannot return a logical expression. How can this be resolved? Note that I do not want to put all expressions into the same Expr type since it makes generating valid random ASTs with QuickCheck impossible. Thanks, Joel -- http://wagerlabs.com/

2 3