- Haskell-Cafe - Haskell.org

Haskell - convert postfix expression to binary tree
by Martin Studna 21 Aug '17

21 Aug '17

Hello, I am trying to convert postfix expression to binary tree. My function takes as argument a list of tokens (strings). Everytime I give the function any input, debugger writes a message: Non-exhaustive patterns in function "add". My idea was: read a token after token and determine, if it is an operator or an operand. If it is operand, don't save any node to the tree and store the number to the stack. Otherwise I create a node with an operator, pop symbols from stack, set them as children of new node and push the operator to stack. If the list of strings is empty, functions print the binary tree. Would someone explain to me, why the function gives non-exhaustive patterns error and how can I fix the function? data Tree = Leaf String | Empty | Node Tree String Tree deriving (Show) add :: Tree -> [String] -> [Tree] -> Tree add (Node l v p) [] stack = (Node l v p) add Empty (x:xs) [] | x `elem` ["*","-","+"] = add (Leaf x) xs [Leaf x] | otherwise = add Empty xs [Leaf x] add Empty (x:xs) (a:b:bs) | x `elem` ["*","-","+"] = add (Node b x a) xs (Leaf x:a:b:bs) | otherwise = add Empty xs (Leaf x:a:b:bs) add (Leaf x) token (a:b:bs) | x `elem` ["*","-","+"] = add (Node b x a) token (Leaf x:bs) | otherwise = Leaf x add (Node l v p) (x:xs) (a:b:bs) | x `elem` ["*","-","+"] = add (Node b x a) xs (Leaf x:bs) | otherwise = add (Node l v p) xs (Leaf x:a:b:bs) parse :: String -> Tree parse input = add Empty (words (toPostfix input)) []

2 1

[ANN] arrowp-qq: an arrowp refresh
by Jose Iborra López 21 Aug '17

21 Aug '17

Dear all, In case anyone finds it useful, there is a new version of arrowp in Hackage that improves the original with a much needed coat of fresh paint. Notable features include a new parser based on haskell-src-exts, a quasi quoter for arrow syntax, and improved desugaring for static choices. https://github.com/pepeiborra/arrowp <https://github.com/pepeiborra/arrowp> The package is in Hackage as **arrowp-qq** due to the impossibility to contact with Ross Paterson (Ross, if you are reading this, please send email!). https://hackage.haskell.org/package/arrowp-qq <https://hackage.haskell.org/package/arrowp-qq> For those of you reading this and wondering why would you want to use a preprocessor for something that GHC can already do, the short answer is that you probably don’t. Using the `proc` quasi quoter --------------------------- ``` addA :: Arrow a => a b Int -> a b Int -> a b Int addA f g = [proc| x -> do y <- f -< x z <- g -< x returnA -< y + z |] ``` Comparison with **arrowp** ----------------------- **arrowp-qq** extends the original **arrowp** in three dimensions: 1. It replaces the `haskell-src` based parser with one based on `haskell-src-exts`, which handles most of GHC 8.0.2 Haskell syntax. 2. It provides not only a preprocessor but also a quasiquoter, which is a better option in certain cases. 3. It extends the desugaring to handle static conditional expressions (currently only if-then-else). Example: ``` proc inputs -> do results <- processor -< inputs if outputResultsArg then outputSink -< results else returnA -< () returnA -< results ``` The standard **arrowp** (and GHC) desugaring for this code is: ``` = ((processor >>> arr (\ results -> (results, results))) >>> (first (arr (\ results -> if outputResultsArg then Left results else Right ()) >>> (outputSink ||| returnA)) >>> arr (\ (_, results) -> results))) ``` This requires an `ArrowChoice`, but there is a more efficient desugaring which performs the choice at compile time and thus an `Arrow` suffices: ``` ((processor >>> arr (\ results -> (results, results))) >>> (first (if outputResultsArg then outputSink else arr (\ results -> ())) >>> arr (\ (_, results) -> results))) ``` Comparison with **GHC** ----------------------- The GHC desugarer does not do a very good job of minimizing the number of `first` calls inserted. In certain `Arrow` instances, this can have a material effect on performance. Example: ``` trivial = proc inputs -> do chunked <- chunk -< inputs results <- process -< chunked returnA -< results ``` This code ought to desugar to a chain of arrows, and indeed, both arrowp and arrowp-qq desugar this to: ``` trivial = chunk >>> process ``` However GHC will produce (approximately) the following code: ``` arr(\inputs -> (inputs,inputs)) >>> first chunk >>> first process >>> arr fst ``` Thanks, Jose Iborra

1 0

Prevent a type parameter from sharing some of its parameters with another parameter
by Timotej Tomandl 21 Aug '17

21 Aug '17

As the title says. Motivation: in a mutable code I want to keep some parameters strictly immutable, i.e. not sharing s with the whole mutable type I think this is best illustrated by 2 examples: 1. abstract example: imagine I have a type X a b c and another type Y a b and I want to prevent any case where the first parameter of X "a" is shared with it's third parameter "c" i.e. X a b (Y a a), X a b (Y a b), X a b (Y b a), X a b (Y a d) etc., any nestings in Y referencing a etc. but allow X a b (Y b b), X a b (Y b c) and any other combination not ruled out above 2. concrete example: imagine I have a type: Item s element key where s is used in the same way as in STRef s a, i.e. it cannot leak outside of a certain context, but I want the key to be immutable i.e. independent of s under any circumstences, so I can't write a type like: Item s element (STRef s refType) this is equivalent to disallowing X a b (Y a d) in 1. Is there any way to write a restriction like this in Haskell? -- Timo

3 3

Ternary infix expression parser
by Jeffrey Brown 19 Aug '17

19 Aug '17

I want to write a parser that lets someone write "(a #uses b) #because (c #needs d)" and read it into a tree: data Tree = Tree String Tree Tree | Leaf String magic "(a #uses b) #because (c #needs d)" = Tree "because" (Tree "uses" (Leaf "a") (Leaf "b")) (Tree "needs" (Leaf "c") (Leaf "d")) I thought I could use Text.Megaparsec.Expr for it, but now I realize it hadnles binary operations, and this is a ternary one. Suggestions? -- Jeff Brown | Jeffrey Benjamin Brown Website <https://msu.edu/~brown202/> | Facebook <https://www.facebook.com/mejeff.younotjeff> | LinkedIn <https://www.linkedin.com/in/jeffreybenjaminbrown>(spammy, so I often miss messages here) | Github <https://github.com/jeffreybenjaminbrown>

3 3

haskell-src-exts 8.2 compatible release
by Matthew Pickering 18 Aug '17

18 Aug '17

Hi all, I realise that people will be starting to use haskell-src-exts libaries with the new GHC 8.2 release. However, I do not have time in the foreseeable future (~ 1-2 months) to be able to implement the necessary parts to support the new language features. The way to make an 8.2 compatible release happen sooner is to send me some patches! There are some pull requests which I would like to merge but require minor changes or rebasing and also a few language features which need implementing. https://github.com/haskell-suite/haskell-src-exts/milestones/1.18 None of them look very difficult to implement unlike other language changes in past releases. I started to work on what was necessary a few months ago but didn't make a large amount of progress. https://github.com/haskell-suite/haskell-src-exts/tree/ghc-8.2 Anyone's help contributing to this important but menial library would be greatly appreciated. Thanks, Matt

2 1

[ANN] Speculate: automatically discover properties about Haskell functions generalization of counter-examples
by Rudy Matela 17 Aug '17

17 Aug '17

Hello, I am happy to announce Speculate. A library to automatically discover properties about Haskell functions. https://hackage.haskell.org/package/speculate Quick example -- discovering properties about addition and multiplication: $ cabal update $ cabal install speculate $ ghci > import Test.Speculate > speculate args{constants = [constant "+" (+), constant "*" (*)]} _ :: Integer (+) :: Integer -> Integer -> Integer (*) :: Integer -> Integer -> Integer x + y == y + x x * y == y * x (x + y) + z == x + (y + z) (x * y) * z == x * (y * z) (x + x) * y == x * (y + y) x <= x * x Speculate is similar to QuickSpec, but uses a different algorithm to produce inequalities and coditional equations -- see README for details. Speculate is available on both Stackage (nightly) and Hackage. -- Rudy

1 0

Re: [Haskell-cafe] cabal update problem?
by Jonathon Delgado 17 Aug '17

17 Aug '17

01-index.tar.gz is also 4 times the size of 00-index.tar.gz

2 2

DataHaskell impromptu workshop at ICFP'17 ?
by Marco Zocca 16 Aug '17

16 Aug '17

Dear all, among those that will attend the last three days of ICFP (i.e. the Haskell symposium and CUFP), are there people who would be interested in meeting to discuss possible future directions for the DataHaskell project? Looking forward to your feedback; Best, Marco

2 1

cabal update problem?
by yi lu 16 Aug '17

16 Aug '17

Hi all, I find cabal 2.0.0.0 brings new change both in downloading package list and the hackage mirror. 1) 00-index.tar.gz has be replaced by 01-index.tar.gz 2) If timestamp.json exists and it is new enough, 01-index.tar.gz won't download, even though I don't have the latest copy of 01-index.tar.gz. So my questions are 1) What else has been changed to hackage.haskell.org mirror? I found four more files: mirrors.json root.json snapshot.json timestamp.json 2) Is it a feature or a bug? Yours, Yi

1 0

123
by Dmitriy Matrosov 16 Aug '17

16 Aug '17

Hi. Is there a way to avoid `UndecidableInstances` in following code: data A f = A {_a1 :: f String} instance Show (f String) => Show (A f) where it does not compile with 1.hs:4:10: error: • The constraint ‘Show (f String)’ is no smaller than the instance head (Use UndecidableInstances to permit this) • In the instance declaration for ‘Show (A f)’ Though, initially, this was {-# LANGUAGE RankNTypes #-} data A f = A {_a1 :: f String} instance forall f a. Show (f a) => Show (A f) where which also does not compile with 1.hs:5:10: error: • Variable ‘a’ occurs more often in the constraint ‘Show (f a)’ than in the instance head (Use UndecidableInstances to permit this) • In the instance declaration for ‘Show (A f)’ The error is different and i don't sure, that this two cases are related. I want these instances to make a type with many records parametrized by `Alternative` type, e.g. data Volume t = Volume { _volName :: t Name , _volSize :: t Size , _volPath :: t Path , _pool :: t Pool } When i try to make instances, which require `*` type, i will end with above cases. -- Dmitriy

4 4