February 2011 - Haskell-Cafe

Beginner: (Another) Binary Search Tree Question
by htc2011 12 Feb '11

12 Feb '11

Hi all, I just started learning Haskell but am having some trouble getting the insertion into a binary search tree to work and was hoping that somebody could advise me on a possible solution. Thanks. Given the data type definition of the tree to be: Code: data Ord a => BST a = EmptyBST | Node ( BST a ) a ( BST a ) deriving (Show, Eq) And the insertion function to be: Code: insert v EmptyBST = Node EmptyBST v EmptyBST insert v (Node b a c) | v<= a = Node a ( insert v b ) c | otherwise = Node a b ( insert v c ) GHCI keeps telling me that I 'cannot construct an infinite type': ' Occurs check: cannot construct the infinite type: a = BST (BST a) Expected type: BST a -> BST (BST a) -> a Inferred type: BST a -> BST (BST a) -> BST (BST a) In the second argument of `Node', namely `(insert v b)' In the expression: Node a (insert v b) c' Upon adding the following signature: Code: insert :: Ord a => a -> BST a -> BST a I get: Occurs check: cannot construct the infinite type. Sorry, but I'm quite lost. Any thoughts? Thanks. Benjamin -- View this message in context: http://haskell.1045720.n5.nabble.com/Beginner-Another-Binary-Search-Tree-Qu… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

3 3

ANN: bytestring-trie 0.2.3
by wren ng thornton 12 Feb '11

12 Feb '11

-------------------------------------------- -- bytestring-trie 0.2.3 -------------------------------------------- A long-awaited release for efficient finite maps from (byte)strings to values. This version adds a number of new functions for taking advantage of the trie structure. At the Haskell Symposium 2010, Milan Straka presented a wonderful paper comparing the state of the @containers@ library pre-GHC7. In it he compared the new @hashmap@ against the buggy old @bytestring-trie@ 0.1.4 (the major bug was fixed in 0.2.2 released 2010-06-10), and I've been meaning to update the package ever since. I haven't had a chance to do an extensive performance analysis yet, but it's worth clearing up some misconceptions--- which is what this release is all about. If you are only interested in being able to associate strings to values, then you may prefer the @hashmap@ package which is faster for those only needing a map-like structure. This package is intended for those who need the extra capabilities that a trie-like structure can offer (e.g., structure sharing to reduce memory costs for highly redundant keys, taking the submap of all keys with a given prefix, contextual mapping, extracting the minimum and maximum keys, etc.) While hacking on another project I noticed that @bytestring-trie@ didn't actually export many functions taking advantage of the trie structure. So let's fix that! -------------------------------------------- -- Changes (available in 0.2.2, but not announced previously) -------------------------------------------- * Added some functions for treating tries like priority queues (minAssoc, maxAssoc, updateMinViewBy, updateMaxViewBy). Currently these are only exported by Data.Trie.Internal though future releases may re-export them from Data.Trie too. -------------------------------------------- -- Changes (since 0.2.2) -------------------------------------------- * Added Data.Trie.Internal.alterBy_: A variant of 'alterBy' which also allows modifying the sub-trie. This is useful for cases where you want to alter a number of values which are each prefixes of one another (e.g., "a", "ab", "abc",...). * Added a number of "contextual" mapping functions (contextualMap, contextualMap', contextualFilterMap, contextualMapBy) which give access to the sub-trie rooted at each value. Currently these are only exported by Data.Trie.Internal though future releases may re-export them from Data.Trie too. * Added strict variants of a number of functions in Data.Trie.Convenience (fromListWith', insertWith', insertWithKey', unionWith'). * Added some additional functions for building tries from association lists (fromListWith', fromListWithL, fromListWithL') as suggested by Ian Taylor. * Converted the definitions for fmap, foldMap, traverse, and filterMap to use the worker/wrapper transform. This appears to be an optimization, though I don't have a decent benchmarking suite for verifying this. * Lots of tweaks and improvements to the documentation. -------------------------------------------- -- Future work -------------------------------------------- * I'm still not leased with the situation of having so many different variants of fromList. There must be a nicer solution which generalizes over all of them and doesn't have the various pessimal corner cases... * The priority queue functions still need some work to make them general as well as comprehensive like the other functions in Data.Trie.Internal are. * I still need to do a thorough performance analysis. The code for Data.Trie was based very closely on the code for Data.IntMap. Milan Straka found a number of ways to optimize the Data.IntMap code, so I need to incorporate those into the Data.Trie code. -------------------------------------------- -- Links -------------------------------------------- Homepage: http://code.haskell.org/~wren/ Hackage: http://hackage.haskell.org/package/bytestring-trie Darcs: http://community.haskell.org/~wren/bytestring-trie/ Haddock (Darcs version): http://community.haskell.org/~wren/bytestring-trie/dist/doc/html/bytestring… -- Live well, ~wren

1 0

Introducing monad-embed
by Tim Maxwell 12 Feb '11

12 Feb '11

Hi, monad-embed is an experimental programming language that parameterizes everything on a monad by default. Examples, source code, etc. are at <http://timmaxwell.org/pages/monad-embed/>. I posted about it on the Haskell subreddit a few months ago (see <http://bit.ly/cUZvrB>) but I was advised to re-post it in haskell-cafe as well. Tim Maxwell

1 0

Re: [Haskell-cafe] Compiling network-bytestring with ghc7+hp2011
by Magnus Therning 12 Feb '11

12 Feb '11

On Fri, Feb 11, 2011 at 04:48:28PM -0800, Johan Tibell wrote: > Hi Magnus, > > network-2.3 supersedes network-bytestring as the modules provided by > the latter were merged into network. network-2.3 and later cannot be > used together with network-bytestring, in one package, as both > expose the same modules. Libraries that use network-bytestring > should eventually migrate to network-2.3. Excellent, I wasn't aware of this. I suggest that the Hackage entry for network-bytestring is modified to let users know this. I noticed that monads-fd has been marked as obsolete on Hackage, with a pointer to mtl, maybe it's possible to do something similar with network-bytestring? /M -- Magnus Therning OpenPGP: 0xAB4DFBA4 email: magnus(a)therning.org jabber: magnus(a)therning.org twitter: magthe http://therning.org/magnus

1 0

Re: [Haskell-cafe] hledger: mtl vs transformers
by Simon Michael 11 Feb '11

11 Feb '11

On Feb 11, 2011, at 11:20 AM, Peter Simons wrote: > If hledger offers optional features by means of Cabal flags, then > users > of the library need the ability to depend on hledger with a specific > set > of features (flags) enabled or disabled, but unfortunately Cabal can't > do that. > > The new approach remedies that problem by placing optional features in > separate packages. That creates a different problem, however, because > users may now install hledger and hledger-web separately, which -- > as we > know -- may create all kinds of version conflicts that are non-trivial > to resolve. > > This is the problem you're now trying to solve by over-specifying the > dependencies of hledger. Arguably, though, Cabal should solve that > problem for the user, i.e. by offering to re-compile hledger to > resolve > the conflict etc., but unfortunately Cabal can't do that either. Hi Peter.. thanks for the follow-up. In case it wasn't clear, I do realise now that attempts to over-specify depedencies to avoid practical cabal install issues can backfire, and a package author should just accept that cabal install can't be made 100% reliable installation method for non-experts (for now - I know many people are thinking about this). And, I've fixed/relaxed the process dependency in hledger head, and only laziness/business has prevented that from being released to hackage. I'll do that asap. Cheers - Simon

1 0

Haskell Help
by PatrickM 11 Feb '11

11 Feb '11

I'm writting a function that will remove tautologies from a fomula.The basic idea is that if in a clause, a literal and its negation are found, it means that the clause will be true, regardless of the value finally assigned to that propositional variable.My appoach is to create a function that will remove this but for a clause and map it to the fomula.Of course I have to remove duplicates at the beginning. module Algorithm where import System.Random import Data.Maybe import Data.List type Atom = String type Literal = (Bool,Atom) type Clause = [Literal] type Formula = [Clause] type Model = [(Atom, Bool)] type Node = (Formula, ([Atom], Model)) removeTautologies :: Formula -> Formula removeTautologies = map tC.map head.group.sort where rt ((vx, x) : (vy, y) : clauses) | x == y = rt rest | otherwise = (vx, x) : rt ((vy, y) : clauses) Now I have problems when I try to give it a formula (for example (A v B v -A) ^ (B v C v A)).Considering that example the first clause contains the literals A and -A. This means that the clause will always be true, in which case it can be simplify the whole set to simply (B v C v A) . But I get the following Loading package old-locale-1.0.0.2 ... linking ... done. Loading package time-1.1.4 ... linking ... done. Loading package random-1.0.0.2 ... linking ... done. [[(True,"A"),(True,"B")*** Exception: Assignment.hs:(165,11)-(166,83): Non-exhaustive patterns in function rt What should I do? -- View this message in context: http://haskell.1045720.n5.nabble.com/Haskell-Help-tp3381647p3381647.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

2 1

Haskell Help
by Patrick M 11 Feb '11

11 Feb '11

I'm writting a function that will remove tautologies from a fomula.The basic idea is that if in a clause, a literal and its negation are found, it means that the clause will be true, regardless of the value finally assigned to that propositional variable.My appoach is to create a function that will remove this but for a clause and map it to the fomula.Of course I have to remove duplicates at the beginning. module Algorithm where import System.Random import Data.Maybe import Data.List type Atom = String type Literal = (Bool,Atom) type Clause = [Literal] type Formula = [Clause] type Model = [(Atom, Bool)] type Node = (Formula, ([Atom], Model)) removeTautologies :: Formula -> Formula removeTautologies = map tC.map head.group.sort where rt ((vx, x) : (vy, y) : clauses) | x == y = rt rest | otherwise = (vx, x) : rt ((vy, y) : clauses) Now I have problems when I try to give it a formula (for example (A v B v -A) ^ (B v C v A)).Considering that example the first clause contains the literals A and -A. This means that the clause will always be true, in which case it can be simplify the whole set to simply (B v C v A) . But I get the following Loading package old-locale-1.0.0.2 ... linking ... done. Loading package time-1.1.4 ... linking ... done. Loading package random-1.0.0.2 ... linking ... done. [[(True,"A"),(True,"B")*** Exception: Assignment.hs:(165,11)-(166,83): Non-exhaustive patterns in function rt What should I do?

1 0

How to write type-level lambda-abstractions at the value level
by oleg＠okmij.org 11 Feb '11

11 Feb '11

HList programming -- as programming with too revealing type systems in general -- is quite tedious. Since the type of an HList value reveals its structure, including the number of the elements and their sequence, we often have to write an HList algorithm twice. We have to program the operation on HList values, using ordinary Haskell. We also have to write the corresponding operation on types, using this time the emergent programming language built, by accident, into the type system. In HList programming, the value- and type- operations are almost the same. For example, to take the head of an HList, we have to extract the first element of the value-level and of the type-level cons-cells. It offends the lazy programmer having to implement the same algorithm twice. What adds injury to the insult is that the type-level language is quite different from the value-level one. The type-level language is untyped, leading to difficult-to-find errors and puzzling error messages. Second, it is not quite higher-order: there seem to be no type-level lambdas. We offer a sedative, showing how to write even higher-order HList operations only once, in one piece of code, from which value- and type- level transformations are derived by the compiler. The key was to bring the type-level language closer to Haskell, in particular, by using lambda-abstractions with named, humanly readable variables. Our unified type-value code relies on the applicative notation, taking it to unintended extremes (hence we call it ultra-applicative). Along the way we find that a form of the first-class, bounded polymorphism has existed in Haskell all along. The goals of unifying value- and type-level HList programming and improving error diagnosis have been set and achieved (albeit perhaps a bit painfully) in Jeff Polakow's recent article: Improving HList programming/debugging (longish) http://www.haskell.org/pipermail/haskell-cafe/2011-January/088168.html which has been the inspiration for the present message. The main difference is ours use of lambda-calculus with named variables to program HList operations. Jeff Polakow has used combinator calculus (the point-free notation), which may become abstruse. Whereas Jeff Polakow relied on GADTs to add a compiler-run--time checking, we avoid GADTs, using the standard tagging approach. At least on Jeff Polakow's examples, GHC reports the same error diagnostics. We borrow Jeff Polakow's main example, writing filter in terms of fold. Here is the (value-level) code for ordinary Haskell lists: > vfilter :: (a -> Bool) -> [a] -> [a] > vfilter p = foldr f [] > where f x v = if p x then x : v else v Here is Jeff Polakow's filter code for HLists: > hFltr p = hFoldr ((Uncurry :$ (HIf Fst Snd)) :. (p :&&& (Cons :&&& > (Flip :$ Const)))) Nil Here is our filter for HLists: > hFilter3 p = hFoldr f nil > where f = lam (X,(V,())) > (HIF (p <$> var X) > (HCONS <$> var X <*> var V) > (var V)) The code ostensibly specifies the operation on HList values. However, it also specifies the corresponding operation on HList types, which we can see from the inferred type of hFliter3: > *TypeLambdaVal> :t hFilter3 > hFilter3 > :: (HFOLDR > (LAM > (X, (V, ())) > (HIF > (A (HConst x) (Lookp X)) > (A (A (HConst HCONS) (Lookp X)) (Lookp V)) > (Lookp V))) > (HList Nil) > xs > res) => > x -> HList xs -> res Here is the sample application, to the HList > l1 = (hTrue *: "a" *: () *: nil) *: > (hFalse *: 'b' *: nil) *: > (hTrue *: nil) *: > nil with the following type and printed value > *TypeLambdaVal> :t l1 > l1 > :: HList > (HList (HBool HTrue :* ([Char] :* (() :* Nil))) > :* (HList (HBool HFalse :* (Char :* Nil)) > :* (HList (HBool HTrue :* Nil) :* Nil))) > *TypeLambdaVal> l1 > [<[<HTrue, "a", ()>], [<HFalse, 'b'>], [<HTrue>]>] The result of filtering has the different printed value, and the matching, also filtered, type: > thF3 = hFilter3 HHead l1 > > *TypeLambdaVal> :t thF3 > thF3 > :: HList > (HList (HBool HTrue :* ([Char] :* (() :* Nil))) > :* (HList (HBool HTrue :* Nil) :* Nil)) > *TypeLambdaVal> thF3 > [<[<HTrue, "a", ()>], [<HTrue>]>] The complete code of the article is available at http://okmij.org/ftp/Haskell/TypeLambdaVal.hs We comment on the salient points below. We skip the discussion of error diagnostics; please see the comments in the code. Our workhorse is the class Apply, which has been defined and used already in the HList library. Its other notable applications are second-order typeclass programming http://okmij.org/ftp/Haskell/types.html#poly2 type-level lambda-calculus http://okmij.org/ftp/Haskell/types.html#computable-types > class Apply f x res | f x -> res where > apply :: f -> x -> res Jeff Polakow's message also relies on Apply, calling it HEval. We prefer the name Apply, because of the following, `natural' instance > instance a ~ a' => Apply (a -> b) a' b where > apply = ($) We starts with a simpler example, of > safe_head :: [a] -> Maybe a > safe_head lst = if null lst then Nothing else Just (head lst) and its implementation for HLists, which is subtle. The standard Haskell function `head' is partial, which is a source of much grief -- but also permitting the simple safe_head code above, which includes (head lst) as a sub-expression. The argument lst may well be the empty list. The type checker does permit applications of `head' to a potentially empty list. That application is guarded by the 'null lst' test and so it will not be executed, and so safe_head is safe indeed. At type-level, things are different: hHead is the total function. The application to the empty HList won't type, regardless of whether it will be executed. We solve the problem with the applicative IF expression, and write hsafe_head simply as > hsafe_head lst = > hif HNull (const HNothing) > (\lst -> HJust (apply HHead lst)) > lst When it comes to iterative computations, we have no such luck. We try > hFilter1 p = hFoldr f nil > where > f (x,(v,())) = hif p (\x -> x *: v) (const v) x (assuming the appropriately defined foldr on HList), which does type check. The inferred type however hFilter1 :: (Apply test t (HBool b), Apply (HIF' (x -> HList (x :* xs)) (b1 -> HList xs)) (HBool b, t) res, HFOLDR ((t, (HList xs, ())) -> res) (HList Nil) xs1 res1) => test -> HList xs1 -> res1 points out the problem, which shows up we try to apply hFilter1: > thF1 = hFilter1 HHead l1 > Couldn't match expected type `HFalse' against inferred type `HTrue' The type of hFilter1 can be written as hFilter1 :: forall t x xs b1 b test xs1 res1. (Apply test t (Bool b), ...) => test -> HList xs1 -> res1 or, in other words, hFilter1 :: forall test xs1 res1. (exists t x xs b1 b. Apply test t (Bool b), ...) => test -> HList xs1 -> res1 But we need hFilter1 :: forall test xs1 res1. (forall t x xs b1 b. Apply test t (Bool b), ...) => test -> HList xs1 -> res1 We need first-class polymorphism. Moreover, we need first-class bounded polymorphism, a first-class polymorphic value with type-class constraints. We eventually get it, by programming the lambda-calculus interpreter with human-readable variable names. The result, the hFilter3 code, was shown at the beginning of the message. Please see the complete code for further details. We only mention the implementation of the beta-reduction: > instance Apply body (ENV v arg) res => Apply (LAM v body) arg res where > apply (LAM body) arg = apply body ((ENV arg) :: ENV v arg) We have confirmed that everything is indeed up to interpretation. We may introduce any notation so long as we could interpret it. Solving a problem in an unusual language by first writing a lambda-calculus interpreter in that language is a good strategy. Interpreting lambda-calculus is sure subtle, yet can be done in many languages, even the ones that were never intended as programming languages, such as C++ templates, Haskell multi-parameter type classes with functional dependencies, or Scheme syntax-rules. Scheme syntax-rules is another example of making use of an odd-ball language by first writing a lambda-calculus interpreter for it. The approach was taken quite far, to the Scheme -to- syntax-rules compiler http://okmij.org/ftp/Scheme/macros.html#Macro-CPS-programming Given (a well-tested) procedure written in a subset of Scheme, the compiler outputs a syntax-rule macro that effects the same computation at the compile-time. Syntax-rules macros are _nothing_ like value-level Scheme code (for example, syntax-rule macros are not applicative). The only publicly known practical application is stress-testing macro-expanders: http://okmij.org/ftp/Scheme/macros.html#syntax-rule-stress-test executing the (compiled from Scheme) syntax-rule that tests if 5 is prime. The macro implements the sieve of Eratosthenes. There has been one macro-expander that crashed, taking down the OS, FreeBSD, with it. That is the only case known to me of a macro and a primality test crashing the operating system.

1 0

Haskell Summers of Code retrospective (updated for 2010)
by Gwern Branwen 11 Feb '11

11 Feb '11

2 years ago in February 2009, I wrote up a history of Summers of Code through 2008 (http://www.haskell.org/pipermail/haskell-cafe/2009-February/055489.html) But the Wheel turns, and years come and pass, leaving memories that fade into 404s; a wind rose in Mountain View, whispering of the coming Summer... I have considerably expanded and updated the coverage: http://www.gwern.net/Haskell%20Summer%20of%20Code.html It now covers the 2009 & 2010 SoCs, adds scads of links, flips the appraisal of some of the older SoCs as time passed and more info came to light, and adds a section discussing 12 proposals from the subreddit & Trac. (It's long enough that I don't feel comfortable copying it inline as I did 2 years ago.) -- gwern http://www.gwern.net

2 1

MissingH won't upgrade
by Andrew Pennebaker 10 Feb '11

10 Feb '11

Specs: - cabal-install 0.8.2 - Cabal 1.8.0.6 - GHC 6.12.3 - Mac OS X 10.6.6 - MacBook Pro 5,1 $ cabal upgrade missingh Resolving dependencies... Configuring regex-base-0.93.2... Preprocessing library regex-base-0.93.2... Building regex-base-0.93.2... [1 of 4] Compiling Text.Regex.Base.RegexLike ( Text/Regex/Base/RegexLike.hs, dist/build/Text/Regex/Base/RegexLike.o ) [2 of 4] Compiling Text.Regex.Base.Context ( Text/Regex/Base/Context.hs, dist/build/Text/Regex/Base/Context.o ) [3 of 4] Compiling Text.Regex.Base ( Text/Regex/Base.hs, dist/build/Text/Regex/Base.o ) [4 of 4] Compiling Text.Regex.Base.Impl ( Text/Regex/Base/Impl.hs, dist/build/Text/Regex/Base/Impl.o ) Registering regex-base-0.93.2... Installing library in /Users/andrew/.cabal/lib/regex-base-0.93.2/ghc-6.12.3 Registering regex-base-0.93.2... Configuring regex-posix-0.94.4... Preprocessing library regex-posix-0.94.4... Building regex-posix-0.94.4... [1 of 6] Compiling Text.Regex.Posix.Wrap ( dist/build/Text/Regex/Posix/Wrap.hs, dist/build/Text/Regex/Posix/Wrap.o ) [2 of 6] Compiling Text.Regex.Posix.String ( Text/Regex/Posix/String.hs, dist/build/Text/Regex/Posix/String.o ) [3 of 6] Compiling Text.Regex.Posix.Sequence ( Text/Regex/Posix/Sequence.hs, dist/build/Text/Regex/Posix/Sequence.o ) [4 of 6] Compiling Text.Regex.Posix.ByteString ( Text/Regex/Posix/ByteString.hs, dist/build/Text/Regex/Posix/ByteString.o ) [5 of 6] Compiling Text.Regex.Posix.ByteString.Lazy ( Text/Regex/Posix/ByteString/Lazy.hs, dist/build/Text/Regex/Posix/ByteString/Lazy.o ) [6 of 6] Compiling Text.Regex.Posix ( Text/Regex/Posix.hs, dist/build/Text/Regex/Posix.o ) Registering regex-posix-0.94.4... Installing library in /Users/andrew/.cabal/lib/regex-posix-0.94.4/ghc-6.12.3 Registering regex-posix-0.94.4... Configuring regex-compat-0.93.1... Preprocessing library regex-compat-0.93.1... Building regex-compat-0.93.1... [1 of 1] Compiling Text.Regex ( Text/Regex.hs, dist/build/Text/Regex.o ) Registering regex-compat-0.93.1... Installing library in /Users/andrew/.cabal/lib/regex-compat-0.93.1/ghc-6.12.3 Registering regex-compat-0.93.1... Configuring MissingH-1.1.0.3... Preprocessing library MissingH-1.1.0.3... Preprocessing executables for MissingH-1.1.0.3... Building MissingH-1.1.0.3... [ 1 of 47] Compiling System.Console.GetOpt.Utils ( src/System/Console/GetOpt/Utils.hs, dist/build/System/Console/GetOpt/Utils.o ) [ 2 of 47] Compiling System.Debian ( src/System/Debian.hs, dist/build/System/Debian.o ) [ 3 of 47] Compiling System.IO.WindowsCompat ( src/System/IO/WindowsCompat.hs, dist/build/System/IO/WindowsCompat.o ) [ 4 of 47] Compiling System.Posix.Consts ( src/System/Posix/Consts.hs, dist/build/System/Posix/Consts.o ) [ 5 of 47] Compiling System.IO.StatCompat ( src/System/IO/StatCompat.hs, dist/build/System/IO/StatCompat.o ) [ 6 of 47] Compiling System.IO.PlafCompat ( src/System/IO/PlafCompat.hs, dist/build/System/IO/PlafCompat.o ) [ 7 of 47] Compiling Data.Compression.Inflate ( src/Data/Compression/Inflate.hs, dist/build/Data/Compression/Inflate.o ) [ 8 of 47] Compiling Data.Hash.MD5.Zord64_HARD ( src/Data/Hash/MD5/Zord64_HARD.lhs, dist/build/Data/Hash/MD5/Zord64_HARD.o ) src/Data/Hash/MD5/Zord64_HARD.lhs:4:2: Bad interface file: /Users/andrew/.cabal/lib/haskell98-1.1.0.0/ghc-6.12.3/Word.hi Something is amiss; requested module haskell98:Word differs from name found in the interface file haskell98-1.1.0.0:Word cabal: Error: some packages failed to install: MissingH-1.1.0.3 failed during the building phase. The exception was: ExitFailure 1 Cheers, Andrew Pennebaker

3 2