- Haskell-Cafe - Haskell.org

HackageDB is not for ... ?
by Andrey Sisoyev 05 Jan '10

05 Jan '10

Hello everybody! I'm planning not a small project, and intuition suggests me, that I should use heavily the rule "separate and rule". So I must separate the project into many maximum independent and general pieces (packages), make them, and finally glue it into my project. The pieces and their dependencies will form an oriented graph without cycles and with overall path finishing into the final project. So far so good I have made two pieces: ** http://hackage.haskell.org/package/PCLT-DB ** http://hackage.haskell.org/package/PriorityChansConverger But I'm coming to understand, that it's not polite to other community members to publish just every package my project will consist of, because we do not want to garbage HackageDB. ------------------------------------- Consider cases: (1) I don't want to publish package A, because I doubt anyone will find it useful. But I develop independent packages B and C, that will be usefull for the community, and want to publish them on Hackage, but they require package A! [Solution] Publish package A, but make it maximum general and complete in itself. (2) I don't want to publish package A, because it's tiny. Well imagine something same popular and useful, like Ord class. 10 lines of code. But I don't want to repeat these lines in every other package. [Solution] Same as for (1) I guess. (3) I don't want to publish package A, because it's about adjacent system. I'm making 3 packages, that all use DBMS (PostgreSQL). All three are thught to be independent. But! They all in their DDL scripts use table inheritance from a common ancestor table "nameables", which is everywhere defined the same: > CREATE TABLE nameables ( -- an ancestor table > name varchar NOT NULL DEFAULT '<name not given>' > , description varchar NULL > , comments varchar NULL > ) TABLESPACE tabsp_pcltcatalogs; > GRANT SELECT, INSERT, UPDATE, DELETE ON TABLE nameables TO > user_someCurrentSchema_data_admin; > GRANT SELECT ON TABLE nameables TO user_someCurrentSchema_data_reader; Now what do I do with that?? The problem gets even more complicated be the fact, that dependent packages may use different DB schemes, so DDL sql script from Nameables will have to be run additionally for them. But that's easy to solve - just decide, whether to add or not by build-depends a comment "-- with DDL init", and maybe additional instruction in README. [Solution] ??? [Solution A] Well, of course, I can pretend that this package may be is Haskellish enough, by inventing something which I don't really need: > data Name = Name { nName :: String, nDescription :: Maybe String, > nComments :: Maybe String } > > class Nameables a where > getName :: a -> Name > > class HasPrimaryKey a => NameableInDBOnly a where > getNameFromDB :: Connection -> a -> IO Name This + sql script and instruction, how to initialize DB. Is it okay to publish this? Looks like garbage... [Solution B] Do my own version control and add same pieces to every package that use Nameable. Don't like this solution. May be I should start using other repository systems like github or darcs, and then this solution will seem more natural to me?.. ---------------------------------- These are my thoughts on the theme. In any case I come to wanting to publish the packages anyway. Probably I miss something in ideology and methodology of using Hackage as community repository. And what do you think about it? Regards, Andrey -- View this message in context: http://old.nabble.com/HackageDB-is-not-for-...---tp27022312p27022312.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

2 2

Compiling a shared library on MacOS X
by Jean-Denis Koeck 05 Jan '10

05 Jan '10

Hello, I'm using the following cabal file to build a shared library with ghc: Build-Type: Simple Executable libmylibrary.dll If os(windows) CPP-Options: -DWIN32 Extensions: ForeignFunctionInterface Build-Depends: ... Main-Is: libmylibrary.hs Ghc-Options: -W --make -no-hs-main -optl-shared -optl-s -O2 The resulting library is called from a C++ graphical user interface (using Qt), which worked great so far on Windows and Linux. However, the compilation fails on MacOS X: Undefined symbols: "_ZCMain_main_closure", referenced from: _ZCMain_main_closure$non_lazy_ptr in libHSrts.a(Main.o) "___stginit_ZCMain", referenced from: ___stginit_ZCMain$non_lazy_ptr in libHSrts.a(Main.o) ld: symbol(s) not found collect2: ld returned 1 exit status I don't know much about shared libraries, even less about them on MacOS X :( Any idea ? Jean-Denis Koeck

5 5

A question on DSL's
by CK Kashyap 04 Jan '10

04 Jan '10

Hi, I am not sure if I'm using DSL in the right context here but I am referring to those solutions that allow us to write code in Haskell and generate a target code source code of another language or even object code for that matter. I am aware of two ways of achieving this - 1. Implement functions that emit the target code - that is, when the Haskell code is compiled and run, the target code is emitted 2. Modify the Haskell compiler's back end to emit the code - that is when the Haskell code is compiled the target code is emitted I am not sure if there are more ways (hybrid perhaps) ... My question is, when would I chose one approach over the other? Regards, Kashyap

5 6

curl on windows?
by Günther Schmidt 04 Jan '10

04 Jan '10

Hi, how can I install curl on windows (XP)? Günther

2 1

HXT XSLT example?
by Günther Schmidt 04 Jan '10

04 Jan '10

Hi, is there a simple example for XSLT via HXT? You know something like take this xml file, apply this xsl file, dump to stdout. Günther

1 0

Why can't we make an instance declaration on a type synonym?
by jberryman 04 Jan '10

04 Jan '10

This may be a dumb question, but why can we not declare a Monad instance of a type synonym? This question came to me while working with the State monad recently and feeling that the requirement that we wrap our functions in the State constructor is a bit... kludgy. Why can't the State monad be defined this way?: > type State s a = \s -> (a , s) > > instance Monad (State s) where > return a = \s -> (a, s) > m >>= k = \s -> let > (a, s') = m s > in k a s' It seems like Haskell's type system could understand the above, but I'm interested in hearing the technical reason which I'm sure exists for why we can't do this. Thanks for any clues, Brandon Simmons http://coder.bsimmons.name/blog/

7 7

Space Efficiency When Sorting a List of Many Lists
by Peter Green 04 Jan '10

04 Jan '10

I'm a Haskell neophyte, so may be missing something obvious in the problem outlined below. I'm fairly proficient in Python + have some limited experience in OCaml and F#, so know just enough to be be dangerous, but not nearly enough to really know what I'm doing here. OK, I have text files containing 'compressed lists' Compressed lists look like this: 8+12,11,7+13,10 1+2+3,1+9,3+6,4 . . Sublists are comma-delimited, and sublist elements are separated by '+' character. I parse these to look like so: [[[8,12],[11],[7,13],[10]], [[1,2,3],[1,9],[3,6],[4]], . . ] I need to explode these and produce a lex-sorted list of exploded lists: [[1,1,3,4],[1,1,6,4],[1,9,3,4],[1,9,6,4],[2,1,3,4],[2,1,6,4],[2,9,3,4], [2,9,6,4],[3,1,3,4],[3,1,6,4],[3,9,3,4],[3,9,6,4], [8,11,7,10],[8,11,13,10],[12,11,7,10],[12,11,13,10]] I then output this data as comma-delimited lists: 1,1,3,4 1,1,6,4 . . 12,11,13,10 I can do all this in my (no doubt fairly naive) program shown below. In real life, one of my test data files contains compressed lists which all contain 7 sublists. This data (correctly) explodes to a list containing ~3,700,000 exploded lists. All good as far as correctly transforming input to output goes. However, sorting the data uses a lot of memory: Partial output from ./explode +RTS -sstderr: 540 MB total memory in use (4 MB lost due to fragmentation) If I do not do any sorting on the exploded lists, i.e. modify the main function to be main = interact (unlines . toCSV . explode . fromCSV . lines) I then see this partial output from ./explode +RTS --stderr: 2 MB total memory in use (0 MB lost due to fragmentation) I can guess that there might be be less laziness and more instantiation when sorting is introduced, but my questions are: (1) Am I doing anything terribly stupid/naive here? (2) If so, what can I do to improve space efficiency? TIA! import Data.List (sort) import Data.List.Split (splitOn) -- Cartesian Product over a List of Lists -- cp [[1,2],[3],[4,5,6]] --> [[1,3,4],[1,3,5],[1,3,6],[2,3,4],[2,3,5], [2,3,6]] cp :: [[a]] -> [[a]] cp [] = [[]] cp (xs:xss) = [y:ys | y <- xs, ys <- cp xss] -- fromCSV ["8+12,11,7+13,10", "1+2+3,1+9,3+6,4"] --> -- [[[8,12],[11],[7,13],[10]],[[1,2,3],[1,9],[3,6],[4]]] fromCSV :: [String] -> [[[Int]]] fromCSV = map parseOneLine where parseOneLine = map parseGroup . splitOn "," where parseGroup = map read . splitOn "+" -- explode [[[1,2],[3],[4,5,6]], [[1, 2], [14,15], [16]]] --> [[1,3,4], [1,3,5], -- [1,3,6],[2,3,4],[2,3,5],[2,3,6],[1,14,16],[1,15,16],[2,14,16], [2,15,16]] explode :: [[[a]]] -> [[a]] explode = concatMap cp -- toCSV [[8,11,7,10,12],[8,11,7,10,12],[8,11,7,10,12]] --> -- ["8,11,7,10,12","8,11,7,10,12","8,11,7,10,12"] toCSV :: (Show a) => [[a]] -> [String] toCSV = map $ tail . init . show --toCSV = map (intercalate "," . map show) main = interact (unlines . toCSV . sort . explode . fromCSV . lines)

6 7

Template Haskell - substitution in pattern in a lambda
by Patrick Caldon 04 Jan '10

04 Jan '10

I'm trying to write some template haskell which will transform: $(buildCP 0) into \(SimpleM d1 d2 d3) (SimpleM _ _ _) -> (SimpleM d1 d2 d3) $(buildCP 1) into \(SimpleM _ d2 d3) (SimpleM d1 _ _) -> (SimpleM d1 d2 d3) $(buildCP 1) into \(SimpleM d1 _ d3) (SimpleM _ d2 _) -> (SimpleM d1 d2 d3) and so on. Ultimately I want to generalize this to more variables. I can't seem to get anything to substitute for the pattern variables in a lambda. Is there a straightforward way of doing this? Below is what I've been playing with to try to make this work. Thanks, Patrick. --- module THTest where import Language.Haskell.TH import qualified Data.Bits type Policy = Int data Management = SimpleM Policy Policy Policy deriving Show -- Compiles - but no substitution for the "aX" and "bX" variables buildCP :: Int -> ExpQ buildCP k = [|\(SimpleM a1 a2 a3) (SimpleM b1 b2 b3) -> (SimpleM $e1 $e2 $e3) |] where (e1,a1,b1) = bitToExprs 0 k (e2,a2,b2) = bitToExprs 1 k (e3,a3,b3) = bitToExprs 2 k -- Won't compile: buildCP2 :: Int -> ExpQ buildCP2 k = [|\(SimpleM $a1 $a2 $a3) (SimpleM $b1 $b2 $b3) -> (SimpleM $e1 $e2 $e3) |] where (e1,a1,b1) = bitToExprs 0 k (e2,a2,b2) = bitToExprs 1 k (e3,a3,b3) = bitToExprs 2 k cp1 0 = \(SimpleM d1 d2 d3) (SimpleM _ _ _) -> (SimpleM d1 d2 d3) {- -- idea is to use in calls like this: cp0 0 = $(buildCP 0) -- should be \(SimpleM d1 d2 d3) (SimpleM _ _ _) -> (SimpleM d1 d2 d3) cp0 1 = $(buildCP 1) -} -- There is also a template haskell [p| ... |] syntax, but not yet implemented ... bitToExprs:: Int -> Int -> (ExpQ,PatQ,PatQ) bitToExprs n k = if Data.Bits.testBit (k::Int) (n::Int) then (e,v1,v2) else (e,v2,v1) where v1 = return WildP v2 = return $ VarP (mkName name) e = return $ VarE (mkName name) name = "d" ++ (show $ n + 1) {- -- ulitmate goal is something like this with 10ish d variables: -- cp0 0 (SimpleM d1 d2 d3 m1) (SimpleM _ _ _ m2) = (SimpleM d1 d2 d3 (me1 m1 m2)) cp0 1 (SimpleM d1 d2 _ m1) (SimpleM _ _ d3 m2) = (SimpleM d1 d2 d3 (me2 m1 m2)) cp0 2 (SimpleM d1 _ d3 m1) (SimpleM _ d2 _ m2) = (SimpleM d1 d2 d3 (me1 m1 m2)) cp0 3 (SimpleM d1 _ _ m1) (SimpleM _ d2 d3 m2) = (SimpleM d1 d2 d3 (me2 m1 m2)) cp0 4 (SimpleM _ d2 d3 m1) (SimpleM d1 _ _ m2) = (SimpleM d1 d2 d3 (me1 m1 m2)) cp0 5 (SimpleM _ d2 _ m1) (SimpleM d1 _ d3 m2) = (SimpleM d1 d2 d3 (me2 m1 m2)) cp0 6 (SimpleM _ _ d3 m1) (SimpleM d1 d2 _ m2) = (SimpleM d1 d2 d3 (me1 m1 m2)) cp0 7 (SimpleM _ _ _ m1) (SimpleM d1 d2 d3 m2) = (SimpleM d1 d2 d3 (me2 m1 m2)) cp0 _ _ _ = (trace "cp0 error" undefined) -}

5 6

setting seed for random numbers
by Larry E. 03 Jan '10

03 Jan '10

I want to set a random seed for a random number generator. I tried this: getSeed = do time <- getClockTime return (ctPicosec (toUTCTime time)) seed <- getSeed randList minval maxval = randomRs (minval,maxval) (mkStdGen seed) But I get the error: parse error on input `<-' which refers to "seed<-getSeed". Using "seed<-getSeed" from the ghci command line works. Why doesn't it work in a script? THe second problem is the seed is of type Integer but mkStdGen wants an Int. How can I get an Int from an Integer? I tried mod to get the seed to within range for an int but the result is still of type Integer how can I coerce Integer to Int when I know result will fit? Thanks

3 2

ANNOUNCE: PriorityChansConverger-0.1
by Andrey Sisoyev 03 Jan '10

03 Jan '10

Hello, cafe! Didn't find it in HackageDB, so made it. http://hackage.haskell.org/package/PriorityChansConverger Category: concurency Converges multiple channels into one. When user reads from the PCC, the choice is made - from which channel to read. System selects a nonempty channel, whose (CurrentPriority, StartPriority) tuple is max. The side effect of the channel selection is it's CurrentPriority decrease by one, if it's value becomes less than one, then the CurrentPriority is set to StartPriority. Based on STM.TChan, extended with capacity control. Version wrapped into is also available. The realization probably isn't very fast and isn't good at memory economy, since it uses fresh high level primitive - STM. It wasn't intended to be used with millions of channels. But it's max throughput comparing to the ordinary Chan throughput is to be estimated (will do it in some future version). Regards, Andrey Sisoyev -- View this message in context: http://old.nabble.com/ANNOUNCE%3A-PriorityChansConverger-0.1-tp26999572p269… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

2 2

Atom's `__global_clock' and `__scheduling_clock'.
by Jason Dusek 03 Jan '10

03 Jan '10

I am mystified by the relationship between Atom's `__global_clock' and the `scheduling_clock'. For example, here is some generated code: /* Includes omitted. */ static uint64_t __global_clock = 0; /* Subroutine declarations omitted. */ void main(void) { { static uint8_t __scheduling_clock = 0; if (__scheduling_clock == 0) { __r0(); /* main.set_up_pins */ __r1(); /* main.set_up_timer */ __scheduling_clock = 0; } else { __scheduling_clock = __scheduling_clock - 1; } } __global_clock = __global_clock + 1; } Looking at code generated by an older version of Atom, it seems like there used not be separate "global" and "scheduling" clocks: /* From http://code.sw17ch.com/blog/atom/blink_atom.c */ void blink_atom(void) { if (__clock % 1 == 0) { r0(); /* blink_atom.decrement */ } if (__clock % 2 == 0) { r1(); /* blink_atom.reset */ } if (__clock % 2 == 1) { r2(); /* blink_atom.flip */ } __clock = __clock + 1; } I would like to know how the `__global_clock' influences execution in the present system. -- Jason Dusek

2 1

lazily-loaded structures
by Jeff Davis 02 Jan '10

02 Jan '10

I'm relatively new to haskell. Let's say I have a simple program like this: import Data.Map type Tree = String type StringMap = Map String String f :: StringMap -> Tree -> Tree f _ y = y ++ "!" getStringMap :: IO StringMap getStringMap = return (Data.Map.fromList [("k1","v1")]) main :: IO () main = do m <- getStringMap s <- getLine putStr $ show (f m s) ++ "\n" Ignore the implementation of f and getStringMap for now. Assume f is a fairly complex function that uses the Map during the process of transforming the Tree argument into the result Tree (here I defined Tree as a string just so that it would compile). getStringMap reads the whole Map into memory at once. However, now let's say that the whole Map is too large, so I decide to store it over a network in a remote database system instead. And then I define another function like: type Connection = String getStringMapValue :: Connection -> String -> IO String that takes a connection string and a key and returns the value. My question is this: how do I change my program to make StringMap a lazily-loaded structure based on getStringMapValue without changing f? Regards, Jeff Davis

3 4

ANN: HPath-0.0.2
by Jason Dusek 02 Jan '10

02 Jan '10

This version of `HPath' depends on new release of `haskell-src-exts' with improved pretty printing. http://hackage.haskell.org/package/HPath-0.0.2 No other changes have been made. -- Jason Dusek

1 0

Linking in Large ByteStrings
by Tom Hawkins 02 Jan '10

02 Jan '10

I have a large tarball I want to link into an executable as a ByteString. What is the best way to do this? I can convert the tarball into a haskell file, but I'm afraid ghc would take a long time to compile it. Is there any way to link constant data directly with ghc? If not, what's the most efficient way to code large ByteStrings for fast compilation?

4 5

ANNOUNCE: restyle-0.1.0
by Daniel Fischer 02 Jan '10

02 Jan '10

I have the pleasure to announce restyle-0.1.0, a tool for the conversion of Haskell source between camelCase and separated_words style. If you want to read your local haddockumentation in your favourite separated-words style, it can do that too, with a liberal choice of separation characters. If you prefer to do your coding in separated_words, it may be as easy as one restyle to then deliver your cool library to the world in the prevalent camelCase (well, it'll probably take a few minor version bumps before that, but we can hope). If you love underscores or hyphens, give it a try. If it sucks, at least it wasn't *your* wasted effort :)

1 0

Timing in atom -- how consistent?
by Jason Dusek 01 Jan '10

01 Jan '10

I'm working with Atom to program an ATtiny25. I am curious about how consistent the timings actually are. Consider John Van Enk' example of blinking a LED on an Arduino: http://code.sw17ch.com/blog/atom/blink_atom.c We see that sometimes `setLED' is executed and sometimes not. When `__clock' is incremented, it will be incremented sometimes sooner, sometimes later. Also, I am a little puzzled by the `__coverage` variable. What does it do? As for my project/motivation -- I'm just trying to blink a little LED on much less robust/rich kit -- the Trippy RGB Waves kit from Lady Ada. I am (gratuitously) exploring ways to program it with Haskell. -- Jason Dusek

3 7

ANN: WFLP 2010 Call for participation
by Pablo Nogueira 01 Jan '10

01 Jan '10

******************************************************************** Call For Participation WFLP2010 19th International Workshop on Functional and (Constraint) Logic Programming Madrid, Spain, January 17, 2010 http://babel.ls.fi.upm.es/events/wflp2010/ ********* colocated with Principles of Programming Languages POPL 2010 http://www.cse.psu.edu/popl/10/ ******************************************************************** IMPORTANT DATES Hotel reservation deadline: December 28, 2009 VENUE WFLP2010 and all POPL'10 affiliated events will take place at the Melia Castilla Hotel, Madrid. REGISTRATION To register for WFLP2010, follow the link from the POPL 2010 page, at http://www.cse.psu.edu/popl/10/ SCOPE The aim of the Workshop on Functional and (Constraint) Logic Programming is to bring together researchers interested in functional programming and (constraint) logic programming with special emphasis on the integration of both paradigms and of other declarative programming extensions. It promotes the cross-fertilizing exchange of ideas and experiences among researchers and students from the different communities interested in the foundations, applications, and combinations of high-level declarative programming languages and related areas. INVITED SPEAKER Mariangiola Dezani (University of Torino, Italy) ACCEPTED PAPERS Transforming Functional Logic Programs into Monadic Functional Programs Bernd Brassel, Sebastian Fischer, Michael Hanus and Fabian Reck Mixed-level Embedding and JIT Compilation for an Iteratively Staged DSL George Giorgidze and Henrik Nilsson An Access Control Language based on Term Rewriting and Description Logic Michele Baggi, Demis Ballis and Moreno Falaschi Lazy and Faithful Assertions for Functional Logic Programs Michael Hanus Parameterized Models for On-line and Off-line Use Pieter Wuille and Tom Schrijvers A Denotational Semantics for Curry Jan Christiansen, Daniel Seidel and Janis Voigtlander A Declarative Debugger of Missing Answers for Functional and Logic Programming Rafael del Vado Virseda and Fernando Perez Morente Efficient and Compositional Higher-Order Streams Gergely Patai Bridging the gap between two Concurrent Constraint Languages Alexei Lescaylle Daudinot and Alicia Villanueva Garcia Large scale random testing with QuickCheck on MapReduce framework Shigeru Kusakabe and Yuuki Ikuta Automated verification of security protocols in tccp Alexei Lescaylle Daudinot and Alicia Villanueva Garcia Implementation and Evaluation of a Declarative Debugger for Java Herbert Kuchen and Christian Hermanns PROGRAM CHAIR Julio Marino (Universidad Politecnica de Madrid, Spain) PROGRAM COMMITTEE Maria Alpuente (Universidad Politecnica de Valencia, Spain) Sergio Antoy (Portland State University, USA) Bernd Brassel (CAU Kiel, Germany) Olaf Chitil (Univ. of Kent, UK) Rachid Echahed (CNRS-IMAG, France) Santiago Escobar (Universidad Politecnica de Valencia, Spain) Moreno Falaschi (Universita di Siena, Italy) Murdoch Gabbay (Heriot-Watt University, UK) Maria Garcia de la Banda (Monash University, Australia) Victor Gulias (Lambdastream SL, Spain) Michael Hanus (CAU Kiel, Germany) Herbert Kuchen (Univ. of Muenster, Germany) Francisco Lopez-Fraguas (Universidad Complutense de Madrid, Spain) James Lipton (Wesleyan University, USA) Mircea Marin (Univ. of Tsukuba, Japan) Juan Jose Moreno-Navarro (Ministry of Science & Innovation, Spain) Brigitte Pientka (McGill University, Canada)

1 0

Use of the Try typeclass
by Edward Z. Yang 01 Jan '10

01 Jan '10

Hello all, I am currently playing with the new cadre of failure libraries, and I'm trying to figure out how to use the monadic version of Failure while also getting the Try typeclass, which appears to be the standardized mechanism for marshalling values from specific monads into the failure monad. Unfortunately, it only seems to be defined when I import Control.Failure, and this module is fairly incompatible with Control.Monad.Failure, as demonstrated by this GHCI transcript: ezyang@javelin:~/Documents/tmr$ ghci Prelude> :m +Control.Failure Prelude Control.Failure> :m +Control.Monad.Failure Prelude Control.Failure Control.Monad.Failure> :t failure <interactive>:1:0: Ambiguous occurrence `failure' It could refer to either `Control.Failure.failure', imported from Control.Failure or `Control.Monad.Failure.failure', imported from Control.Monad.Failure I'm using MTL, which might be the reason why there's all sorts of unhappiness. :-) Cheers, Edward

3 8

Haskell Hackathon in Boston January 29th-31st?
by Ravi Nanavati 01 Jan '10

01 Jan '10

After all of the fun I had at Hac Phi, I've been thinking for a while that it would be fun to organize a Boston hackathon (to have all of the hackathon fun without the long drive). After some recent chats with my MIT friends, it seems like the weekend just after IAP (January 29th-January 31st) might be a good one. I've created a page to start organizing this hackathon (which I'm calling HacBOS unless someone comes up with a catchier name) here: http://www.haskell.org/haskellwiki/HacBOS If you'd be interested in attending a Boston hackathon, please add yourself to the possible attendees list on that page. If the proposed weekend does NOT work for you, but you're still interested in attending a Boston hackathon please indicate what other weekends during MIT's IAP (January 4th-January 29th) might work for you. I'm looking forward to making HacBOS happen! Thanks, - Ravi Nanavati

2 1

Announce: data-clist-0.0.3 -- A RingBuffer/CircularList/Ring data type
by John Van Enk 31 Dec '09

31 Dec '09

Hi all, data-clist-0.0.3 is up on hackage: http://hackage.haskell.org/package/data-clist-0.0.3 Any feedback is appreciated. The docs are getting there, but not quite complete. Enjoy! /jve

1 0

Lifting monad syntax sugar
by Maciej Piechotka 31 Dec '09

31 Dec '09

I'm not quite sure if it exists but with working with lifted monads/lifted arrows it would be useful. Let f be function from m a to n a where m and n are monad (arrows respectivly) for any a then: > do v <- something 0 > lift (f) g <- somethingElse > h <- somethingInLift > i <- somethingCompletlyDifferent v > doSomething g h is syntaxt sugar of > do v <- something 0 > (g, h) <- f $ do g <- somethingElse > h <- something > i <- somethingCompletlyDifferent v > return (g, h) > doSomething g h and > proc (x) -> do v <- something -< x > lift (f) g <- somethingElse -< () > h <- somethingInLift -< () > i <- doSomething -< v > somethingCompletlyDifferent -< (g, h) is syntax sugar of > proc (x) -> do v <- something -< g > (g, h) <- f (proc (v) -> do g <- somethingElse -< () > h <- somethingInLift -< () > i <- doSomething -< v > returnA -< (g, h)) -< v > somethingCompletlyDifferent -< (g, h) I am aware that syntatic sugar is evil (http://www.haskell.org/haskellwiki/Syntactic_sugar/Cons) and therefore I'd prefere to post it here before submitting feature request to ghc (I'll also threat no resoponses as nobody care so why pollute syntax). Regards PS. I'm aware that lift is existing function (Control.Monad.Trans) so possibly other name will be choosen. PPS. Syntax is similar to rec as last line can be binding

1 0

Dynamically Linking Foreign Functions
by Richard Warburton 31 Dec '09

31 Dec '09

Apologies in advance for the length of this email, but I've tried to be as clear as possible. Any help on the matter most appreciated. Goal: I have a simple interpreter for a language that I've written, and I wish to implement an FFI. My ideal api would be like 'ctypes' in python. Here's an example: from ctypes import * libc = CDLL("libc.so.6") libc.printf("An int %d, a double %f\n", 1234, c_double(3.14)) Prints out: An int 1234, a double 3.140000 Implementation: I am currently trying to use the dynamic linker in order to specify the library string, for example the following seems to work: import Foreign import Foreign.C.Types import Foreign.C.String import Monad (liftM) import System.Posix.DynamicLinker type Fun = CString -> IO CInt foreign import ccall unsafe "dynamic" c_printf :: FunPtr Fun -> Fun printf :: String -> IO Int printf str = do withDL "libc.so.6" [RTLD_NOW] $ \dl -> do printf_ptr <- dlsym dl "printf" let fun = c_printf printf_ptr liftM fromIntegral $ withCString str fun main = printf "hello world" Problem: I don't understand how I can generate the foreign import statements at runtime. I am currently considering generating strings of such expressions, and using hs-plugins in order to compile them. This seems like a complete hack though - I'm dynamically loading a haskell library in order to dynamically load a foreign library. Another option is to write a dynamic loader in C, and then call this from haskell, but how would I type the loading function - obviously I can give it a CString for the library, and another for the function in question - but what would the return type be? regards, Richard Warburton

2 3

Is cabal option --extra-lib-dirs working?
by Ahn, Ki Yung 31 Dec '09

31 Dec '09

I had some problem with --extra-lib-dirs option in cabal-install. I've been trying installing bindings-yices package on hackage. Since yices may be installed in non-standard location, such as under your own home directory, one may have to use --extra-include-dirs and --extra-lib-dirs option. --extra-include-dirs work well and locates the header for the yices C binding, but --extra-lib-dirs option does not seem to work well. Would this be a cabal-install bug, or some package misconfiguration? ==================================================== kyagrd@kyavaio:~/tmp/bindings-yices-0.1$ cabal configure Resolving dependencies... Configuring bindings-yices-0.1... cabal: Missing dependency on a foreign library: * Missing header file: yices_c.h * Missing C library: yices This problem can usually be solved by installing the system package that provides this library (you may need the "-dev" version). If the library is already installed but in a non-standard location then you can use the flags --extra-include-dirs= and --extra-lib-dirs= to specify where it is. kyagrd@kyavaio:~/tmp/bindings-yices-0.1$ cabal configure --extra-include-dirs=/home/kyagrd/yices-1.0.21/include Resolving dependencies... Configuring bindings-yices-0.1... cabal: Missing dependency on a foreign library: * Missing C library: yices This problem can usually be solved by installing the system package that provides this library (you may need the "-dev" version). If the library is already installed but in a non-standard location then you can use the flags --extra-include-dirs= and --extra-lib-dirs= to specify where it is. kyagrd@kyavaio:~/tmp/bindings-yices-0.1$ cabal configure --extra-include-dirs=/home/kyagrd/yices-1.0.21/include --extra-lib-dirs=/home/kyagrd/yices-1.0.21/lib Resolving dependencies... Configuring bindings-yices-0.1... cabal: Missing dependency on a foreign library: * Missing C library: yices This problem can usually be solved by installing the system package that provides this library (you may need the "-dev" version). If the library is already installed but in a non-standard location then you can use the flags --extra-include-dirs= and --extra-lib-dirs= to specify where it is. kyagrd@kyavaio:~/tmp/bindings-yices-0.1$ kyagrd@kyavaio:~/tmp/bindings-yices-0.1$ ls /home/kyagrd/yices-1.0.21/include/ yices_c.h yicesl_c.h kyagrd@kyavaio:~/tmp/bindings-yices-0.1$ ls /home/kyagrd/yices-1.0.21/lib/ libyices.a libyices.so kyagrd@kyavaio:~/tmp/bindings-yices-0.1$ ls -al /home/kyagrd/yices-1.0.21/include/ 합계 40 drwxr-xr-x 2 kyagrd kyagrd 4096 2009-07-17 20:58 . drwxr-xr-x 6 kyagrd kyagrd 4096 2009-07-07 23:19 .. -rw-r--r-- 1 kyagrd kyagrd 27948 2009-05-05 19:03 yices_c.h -rw-r--r-- 1 kyagrd kyagrd 1786 2009-05-05 19:03 yicesl_c.h kyagrd@kyavaio:~/tmp/bindings-yices-0.1$ ls -al /home/kyagrd/yices-1.0.21/lib/ 합계 8936 drwxr-xr-x 2 kyagrd kyagrd 4096 2009-12-30 19:29 . drwxr-xr-x 6 kyagrd kyagrd 4096 2009-07-07 23:19 .. -rw-r--r-- 1 kyagrd kyagrd 5167710 2009-05-05 19:03 libyices.a -rwxr-xr-x 1 kyagrd kyagrd 3955648 2009-05-05 19:03 libyices.so

1 0

Re: [Haskell-cafe] Space Efficiency When Sorting a List of Many Lists
by Patai Gergely 31 Dec '09

31 Dec '09

Hi, > explode [[[1,2],[3],[4,5,6]], [[1, 2], [14,15], [16]]] --> [[1,3,4], > [1,3,5],[1,3,6],[2,3,4],[2,3,5],[2,3,6],[1,14,16],[1,15,16], > [2,14,16],[2,15,16]] I don't think the following will solve your problem, but explode can be rewritten with existing functions thanks to the list monad: explode = concatMap sequence Gergely -- http://www.fastmail.fm - A no graphics, no pop-ups email service

1 0

Re: FASTER primes
by Steve 31 Dec '09

31 Dec '09

On Wed, 2009-12-30 at 11:09 -0500, haskell-cafe-request(a)haskell.org wrote: > Am Mittwoch 30 Dezember 2009 01:23:32 schrieb Will Ness: > > Daniel Fischer <daniel.is.fischer <at> web.de> writes: .... > No, it's my own code. Nothing elaborate, just sieving numbers 6k1, > twice as fast as the > haskellwiki code (here) and uses only 1/3 the memory. For the record: > > ---------------------------------------------------------------------- > {-# LANGUAGE BangPatterns #-} > module SievePrimes where > > import Data.Array.Base (unsafeRead, unsafeWrite, unsafeAt) > import Data.Array.ST > import Data.Array.Unboxed > import Control.Monad (when) > import Data.Bits > > primesUpTo :: Integer -> [Integer] > primesUpTo bound > = 2:3:[fromIntegral (3*i + (if testBit i 0 then 4 else 5)) > | i <- [0 .. bd], par `unsafeAt` i] > where > bd0 = 2*(bound `div` 6) - case bound `mod` 6 of { 0 -> 2; 5 -> > 0; _ -> 1 } > bd = fromInteger bd0 > sr = floor (sqrt (fromIntegral bound)) > sbd = 2*(sr `div` 6) - case sr `mod` 6 of { 0 -> 2; 5 -> 0; _ > -> 1 } > par :: UArray Int Bool > par = runSTUArray $ do > ar <- newArray (0,bd) True > let tick i s1 s2 > | bd < i = return () > | otherwise = do > p <- unsafeRead ar i > when p (unsafeWrite ar i False) > tick (i+s1) s2 s1 > sift i > | i > sbd = return ar > | otherwise = do > p <- unsafeRead ar i > when p (let (!start,!s1,!s2) = if even i > then > (i*(3*i+10)+7,2*i+3,4*i+7) else (i*(3*i+8)+4,4*i+5,2*i+3) in tick > start s1 s2) > sift (i+1) > sift 0 > ---------------------------------------------------------------------- > > The index magic is admittedly not obvious, but if you take that on > faith, the rest is > pretty clear. To find the n-th prime, > > ---------------------------------------------------------------------- > module Main (main) where > > import SievePrimes (primesUpTo) > import System.Environment (getArgs) > > printNthPrime :: Int -> IO () > printNthPrime n = print (n, primesUpTo (estim n) !! (n-1)) > > main = do > args <- getArgs > printNthPrime $ read $ head args > > estim :: Int -> Integer > estim k > | n < 13 = 37 > | n < 70 = 349 > | otherwise = round x > where > n = fromIntegral k :: Double > x = n * (log n + log (log n) - 1 + 1.05 * log (log n) / log n) > ---------------------------------------------------------------------- > > If I don't construct the prime list but count directly on the array, > it's ~6% faster. The speed difference varies with the value of 'bound' - the difference between counting directly on the array and creating a list from the array increases as 'bound' increases. I tested it for 10^8 and 10^9 (using Int not Integer) and using the array without creating a list is 50+% faster. It looks like a very fast method for creating the 'set' of primes up to bound. Steve

1 0

ANN: TxtSushi 0.5.0
by Keith Sheppard 31 Dec '09

31 Dec '09

Hello Cafe, I've uploaded a new version of TxtSushi to http://hackage.haskell.org/package/txt-sushi and announced the details here http://blog.keithsheppard.name/2009/12/txtsushi-050.html. TxtSushi is a set of command-line utilities for transforming CSV and tab-delimited files including an SQL based utility. Best Regards Keith -- keithsheppard.name

1 0

on HaskellDBs switch to HList
by Günther Schmidt 30 Dec '09

30 Dec '09

Hello Justin, since you are about to migrate HaskellDB to using HList, do we still need singleton types for the "columns" as before? Günther

1 0

How to get a list of constructors for a type?
by Gregory Propf 30 Dec '09

30 Dec '09

Say I have something like data DT a = Foo a | Bar a | Boo a I want something like a list of the constructors of DT, perhaps as [TypeRep]. I'm using Data.Typeable but can't seem to find what I need in there. Everything there operates over constructors, not types.

3 2

ANN: HPath-0.0.0
by Jason Dusek 30 Dec '09

30 Dec '09

HPath is a command line utility to grab the Haskell source for a given identifier: :; dist/build/hpath/hpath HPath.Path.parse 2>/dev/null parse :: String -> Either ParseError Path parse s = Text.ParserCombinators.Parsec.parse (qualified []) s s This is an alpha release. There are many things HPath can't retrieve -- like constructors -- and there seem to be some complications with the underlying parser/pretty printer (some times you get far too many newlines). There will be another release when the newline issue is resolved. The hope is to release HPath in conjunction with LaTeX macros to allow easy inclusion of Haskell in elaborate documents. -- Jason Dusek

2 3

Preconditions as Typeclasses (Was: Re: Mysterious factorial)
by Luke Palmer 30 Dec '09

30 Dec '09

On Wed, Dec 30, 2009 at 11:15 AM, Ralf Hinze <ralf.hinze(a)comlab.ox.ac.uk> wrote: >> I would use: >> >> foldm :: Monoid m => [m] -> m >> >> Which is just a better implementation of mconcat / fold. The reason I >> prefer this interface is that foldm has a precondition in order to >> have a simple semantics: the operator you're giving it has to be >> associative. I like to use typeclasses to express laws. > > That's a valid point. Unfortunately, Haskell is not Coq, so there > is no guarantee that the monoid laws are actually satisfied. And > using a type-class has the downside that you can have only one > instance per type. Maybe, you want to use both `foldm (+) 0' and > `foldm (*) 1'. So the bottom-line is that you should have both > versions. Well, it's a matter of taste, which I'm trying to argue into convention (eg. http://lukepalmer.wordpress.com/2009/07/01/on-the-by-functions/ ). I mean, if you can do foldm (+) 0, it seems quite reasonable to be able to do foldm (-) 0. However, given: newtype Sum a = Sum a instance (Num a) => Monoid (Sum a) where -- (+) is associative with 0 as its identity mempty = Sum 0 mappend (Sum a) (Sum b) = Sum (a + b) It is not so obvious that you can do: newtype Difference a = Difference a instance (Num a) => Monoid (Difference a) where -- (-) is associative with 0 as its identity NOT mempty = Difference 0 mappend (Difference a) (Difference b) = Difference (a - b) Admittedly it is quite a lot more typing, and I do like brevity, but I also like unverified preconditions to be very loud. Once the tech is there, I would like to require a *proof*, but since proving is still hard and Haskell has no support for it, I need some way to document preconditions. I really like that knowing the name and type of a function is enough to use it most of the time, so documentation isn't really a good place for such preconditions. Typeclasses already have the habit of coming with laws, so I take it to the extreme and encode all my preconditions in typeclasses. It is less convenient. But preconditions that are not verified by the typechecker are rare in Haskell code, and proofs of preconditions are subtle, so let's encourage abstraction and documentation of such proofs. In all places except instances, let's be certain that the typechecker does all of our verification work. Luke

1 0

Mysterious factorial
by Artyom Kazak 30 Dec '09

30 Dec '09

Why fact2 is quicker than fact?! fact2 :: Integer -> Integer fact2 x = f x y where f n e | n < 2 = 1 | e == 0 = n * (n - 1) | e > 0 = (f n (e `div` 2)) * (f (n - (e * 2)) (e `div` 2)) y = 2 ^ (truncate (log (fromInteger x) / log 2)) fact :: Integer -> Integer fact 1 = 1 fact n = n * fact (n - 1) I tried to write tail-recursive fact, fact as "product [1..n]" - fact2 is quicker! fact2 1000000 == fact 1000000 - I tested.

6 10

Finally tagless and abstract relational Algebra
by Günther Schmidt 30 Dec '09

30 Dec '09

Hi, I'm still trying to build an *abstract* Relation Algebra using the finally tagless style. My guess is that finally tagless style allows one to create a syntax without any initial dependency to an implementation. Ie. once one has created the syntax in this style one can then proceed to construct terms. So this is my goal, create a syntax for relational algebra, express an abstract relational algorithm in this syntax and worry about implementation / compilation / evaluation *later*. But at least being able to express a correctly typed term. I presume I will need to employ HList at some point, but I'm not entirely certain where. Will I need it at the very beginning, as constrains in the syntax so that only correct abstract terms can be built, or will I need it in on of the interpreters / compilers later? Günther

6 13

Alternatives to type classes.
by Jason Dusek 30 Dec '09

30 Dec '09

Consider the real numbers. They "are" a group. We have an identity element `0', inverses and closure under the associative operation `+'. Group+ = (+, 0, -1 * _) They are another group, too -- the group with `*': Group* = (*, 1, 1 / _) This seems like a real problem with the whole notion of typeclasses -- we can't really say a set/type "is" its extension with some new operations. One road to go on this is to make every extension of the set with new ops a different type; but that seems really horribly inconvenient. I wonder what approaches have been tried here? -- Jason Dusek

3 3

Re: [Haskell-cafe] (liftM join .) . mapM
by gladstein＠gladstein.com 30 Dec '09

30 Dec '09

I couldn't resist the opportunity for some ascii abstract art. Emacs turns the backquoted bits blue. f `o` g = ( f) . g f `oo` g = (o f) . g f `ooo` g = (oo f) . g f `oooo` g = (ooo f) . g f `ooooo` g = (oooo f) . g f `oooooo` g = (ooooo f) . g f `ooooooo` g = (oooooo f) . g f `oooooooo` g = (ooooooo f) . g f `ooooooooo` g = (oooooooo f) . g f `oooooooooo` g = (ooooooooo f) . g f `ooooooooooo` g = (oooooooooo f) . g f `oooooooooooo` g = (ooooooooooo f) . g f `ooooooooooooo` g = (oooooooooooo f) . g f `oooooooooooooo` g = (ooooooooooooo f) . g f `ooooooooooooooo` g = (oooooooooooooo f) . g f `oooooooooooooooo` g = (ooooooooooooooo f) . g f `ooooooooooooooooo` g = (oooooooooooooooo f) . g f `oooooooooooooooooo` g = (ooooooooooooooooo f) . g f `ooooooooooooooooooo` g = (oooooooooooooooooo f) . g f `oooooooooooooooooooo` g = (ooooooooooooooooooo f) . g

1 0

(liftM join .) . mapM
by Tony Morris 30 Dec '09

30 Dec '09

Can (liftM join .) . mapM be improved? (Monad m) => (a -> m [b]) -> [a] -> m [b] -- Tony Morris http://tmorris.net/

9 15

suffix or operands invalid for `push'
by Martijn van Steenbergen 30 Dec '09

30 Dec '09

Hello, Above error is one of those that appear when using GHC on the 64-bit Snow Leopard. I've already patched my /usr/bin/ghc to mention -optc-m32 -opta-m32 -optl-m32. However, the error still occurs when doing 'cabal haddock' in *some* packages. For example, a local project of mine builds just fine, but trying to cabal haddock the happstack-helpers package goes horribly wrong and no documentation is generated. How do I fix this? And why does it happen only in certain packages? Many thanks, Martijn.

2 3

Perhaps you haven't installed the "dyn" libraries
by Gregory Propf 29 Dec '09

29 Dec '09

I'm trying out the dynamic linking in GHC 6.12 and getting this message a lot for different libraries. I assume I need to rebuild them with different ghc options in the cabal files and have tried -shared, -dynamic and -fPIC but with no luck. Is there something I'm missing.

2 1

Configuring cabal install readline on Snow Leopard with MacPorts
by Alexy Khrabrov 29 Dec '09

29 Dec '09

I've tried to do cabal install readline on Snow Leopard with MacPorts and it fails with the infamous: $ cabal install readline ... checking for GNUreadline.framework... checking for readline... no checking for tputs in -lncurses... yes checking for readline in -lreadline... yes checking for rl_readline_version... yes checking for rl_begin_undo_group... no configure: error: readline not found, so this package cannot be built See `config.log' for more details. cabal: Error: some packages failed to install: readline-1.0.1.0 failed during the configure step. The exception was: exit: ExitFailure 1 Googilng shows the usual explanation that Mac'y broken clone interferes; yet I do have MacPorts and readline 6 there. So I try, per fixes recommended, $ cabal install readline --extra-include-dirs=/opt/local/include --extra-lib-dirs=/opt/local/lib ... checking for rl_readline_version... yes checking for rl_begin_undo_group... no ... -- same result. Downloaded the package and do configure manually: ./configure --with-readline-includes=/opt/local/include --with-readline-libraries=/opt/local/lib ... checking for readline in -lreadline... no checking for rl_readline_version... no ... Huh? $ port contents readline ... /opt/local/include/readline/readline.h ... /opt/local/lib/libreadline.5.0.dylib /opt/local/lib/libreadline.5.1.dylib /opt/local/lib/libreadline.5.2.dylib /opt/local/lib/libreadline.6.0.dylib /opt/local/lib/libreadline.6.dylib /opt/local/lib/libreadline.a /opt/local/lib/libreadline.dylib ... How should I properly tell cabal install readline where my readline is? Cheers, Alexy

4 4

ghc 6.12.1 and regex
by David Fox 29 Dec '09

29 Dec '09

Is anyone else seeing this problem: > :m +Text.Regex.Posix > "\250" =~ "\250" :: Bool True > "\250" =~ "[\250]" :: Bool False

2 3

ghc 6.12.1 and regex
by Paulo Tanimoto 29 Dec '09

29 Dec '09

Oh, I forgot to "reply-to-all". ---------- Forwarded message ---------- From: Paulo Tanimoto <tanimoto(a)arizona.edu> Date: Tue, Dec 29, 2009 at 9:39 AM Subject: Re: [Haskell-cafe] ghc 6.12.1 and regex To: David Fox <ddssff(a)gmail.com> Hi David, On Tue, Dec 29, 2009 at 9:28 AM, David Fox <ddssff(a)gmail.com> wrote: > Is anyone else seeing this problem: > >> :m +Text.Regex.Posix >> "\250" =~ "\250" :: Bool > True >> "\250" =~ "[\250]" :: Bool > False I also get that on GHC 6.10.4. On the other hand: $ cabal update $ cabal install regex-tdfa $ ghci > :m +Text.Regex.TDFA > "\250" =~ "\250" :: Bool True > "\250" =~ "[\250]" :: Bool True But the author says it's not fully Posix yet: http://hackage.haskell.org/package/regex-tdfa Paulo

1 0

semantics of type synonym
by pbrowne 29 Dec '09

29 Dec '09

Hi, I am studying the underlying semantics behind Haskell and to what degree those semantics are actually implemented. I need to clarify what a *type synonym* actual means in relation to Haskell's logic (or formal semantics). I used the following type synonym: type Name = String getName(n) = n I checked the types with two tests: -- test 1 :t "ww" "ww" :: [Char] -- test 2 :t getName("ww") getName("ww") :: Name Obviously I get two different types. In the case of the function Haskells type system seems to pick up enough information to determine that “ww” is a Name. But I am not sure what is happening with the literal "ww" in the first test. Pat

6 9

Performance of functional priority queues
by Richard O'Keefe 29 Dec '09

29 Dec '09

There's a current thread in the Erlang mailing list about priority queues. I'm aware of, for example, the Brodal/Okasaki paper and the David King paper. I'm also aware of James Cook's priority queue package in Hackage, have my own copy of Okasaki's book, and have just spent an hour searching the web. One of the correspondents in that thread claims that it is provably impossible to have an efficient priority queue implementation without mutability. I think he's cuckoo. But I'd like to have some numbers to back me up. Can anyone point me to some actual benchmark results comparing priority queue performance *with* mutation and priority queue performance *without* mutation, in the same functional or mostly-functional language?

16 24

Native CLient
by Joan Miller 29 Dec '09

29 Dec '09

Native CLient (NaCl) [1] is a technology very cool which lets to run native code in web applications, and it's being integrated in some languages as Python [2]. Go [3] already has rudimentary support for Native Client (and it's logical since that both technologies are from Google) I hope that Haskell also gets support for NaCl and doesn't loose this train else a language as Go could get every time more users that until now they had gone to Haskell or Erlang mainly for its concurrency. [1] http://code.google.com/p/nativeclient/ [2] http://lackingrhoticity.blogspot.com/2009/06/python-standard-library-in-nat… [3] http://golang.org/pkg/exp/nacl/

2 3

Invertible functions list
by Jonathan Fischoff 29 Dec '09

29 Dec '09

Hi, I would to create a list of tuples (or something similar) of invertible functions [((a -> b), (b -> a)), ((b -> c), (c -> b)), .... Such that I could call forward invertibleFuctionList domainValue = ? -- composite all the functions backward invertibleFuctionList rangeValue = forward (reverse invertibleFuctionList) rangeValue -- or something similar I would also like to concat them. This sounds like a job for GADT that someone might have already tackled. Any ideas? -Jonathan

5 8

Haskell Platform - distiguish packages in Hackage
by Radoslav Dorcik 29 Dec '09

29 Dec '09

Hello, is it possible to distiguish which package is included at Haskell Platform directly from Hackage web interface or `cabal info` ? So anybody can recognize if the dependecy of his package is going from platform or not without platform installed. Thanks, Rado

1 0

Request to review my attempt at understanding Monads
by CK Kashyap 29 Dec '09

29 Dec '09

Hi, I've been reading the papers titled "Comprehending Monads" and "Monadic Parser Combinator" to understand Monads and I think I am beginning to understand it. In my attempt to validate my understanding, I've written my version of List data structure with Monadic behaviour - I'd appreciate answers to the following queries - 1. Comments about the functions I've written 2. I've used the do notation at the bottom which is a result of my List being a Monad - are there any other benefits that comes in because of List being a Monad? What would MonadPlus provide me? 3. The comprehension syntax for Lists in Haskell - can that be used in anyway for other Monads? Regards, Kashyap import Monad ( MonadPlus(..) ) data List a = Cons a (List a) | Empty deriving Show --myMap :: (t -> a) -> List t -> List a myMap :: (t -> a) -> List t -> List a myMap f Empty = Empty myMap f (Cons a rest) = Cons (f a) (myMap f rest) --myAppend :: List a -> List a -> List a myAppend :: List a -> List a -> List a myAppend Empty l = l myAppend l Empty = l myAppend (Cons a rest) l = Cons a (myAppend rest l) --myConcat :: List (List a) -> List a myConcat :: List (List a) -> List a myConcat Empty= Empty myConcat (Cons Empty rest)= myConcat rest myConcat (Cons list rest)= myAppend list (myConcat rest) instance Monad List where return a = Cons a Empty Empty >>= f = Empty l >>= f = myConcat (myMap f l) instance MonadPlus List where p `mplus` q = myAppend p q mzero= Empty list2myList :: [a] -> List a list2myList [] = Empty list2myList (x:xs) = Cons x (list2myList xs) l1 = list2myList [1..10] l2 = do x <- l1 y <- Cons (2*x) Empty return y

7 9

Design question
by haskell＠kudling.de 29 Dec '09

29 Dec '09

Hi, i am not quite sure how to do this in the most elegant way: I have some data structures: data A = A Double data B = B Double data C = C Double ... and i want to allow only a subset in another data structure, so i did something like this: data SubSet = SubSetA A | SubSetC C and use it in Foo: data Foo = Foo [SubSet] No i want to perform a polymorphic operation on the contents of A,B,C, e.g. doSomething :: Foo -> [Double] doSomething (Foo s) = map doSomethingElse s Now i have two questions: 1) Is the way i define and use "SubSet", the only/valid way to define subsets? 2) What's the best way to make "doSomethingElse" polymorphic? There's the tedious way: doSomethingElse (SubSetA x) = doSomethingElse x doSomethingElse (SubSetB x) = doSomethingElse x or i could make SubSet and A,B,C instances of a type class with the function "doSomethingElse". But i have several different subsets so the type class aproach feels like overkill for these helper structures. Whatever my approach is, it does not feel right. Can you help me step back and get the picture? Thanks, Lenny

6 7

Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve)
by Dave Bayer 29 Dec '09

29 Dec '09

Here is another prime sieve. It is about half the length of the fastest contributed code (ONeillPrimes) and nearly as fast until it blows up on garbage collection: > % cat ONeillPrimes.hs | grep -v "^--" | wc > 185 1105 6306 > % cat BayerPrimes.hs | grep -v "^--" | wc > 85 566 2418 > > [Integer] -O 1*10^6 2*10^6 3*10^6 4*10^6 5*10^6 > --------------------------------------------------------- > ONeillPrimes | 3.555 | 7.798 | 12.622 | 18.927 | 23.529 > BayerPrimes | 3.999 | 8.895 | 18.003 | 22.977 | 38.053 I wrote this as an experiment in coding data structures in Haskell's lazy evaluation model, rather than as explicit data. The majority of the work done by this code is done by "merge"; the multiples of each prime percolate up through a tournament consisting of a balanced tree of suspended "merge" function calls. In order to create an infinite lazy balanced tree of lists, the datatype > data List a = A a (List a) | B [a] is used as scaffolding. One thinks of the root of the infinite tree as starting at the leftmost child, and crawling up the left spine as necessary. What I'm calling a "venturi" > venturi :: Ord a => [[a]] -> [a] merges an infinite list of infinite lists into one list, under the assumption that each list, and the heads of the lists, are in increasing order. This could be a generally useful function. If one can think of a better way to write "venturi", swapping in your code would in particular yield a faster prime sieve. I found that a tertiary merge tree was faster than a binary merge tree, because this leads to fewer suspensions. One can speed this code up a bit by interleaving strict and lazy calls, but I prefer to leave the code short and readable. It is bizarre that > trim p = let f m x = mod x m /= 0 in filter (f p) lurks in the prime sieve code, but it is only used with primes of size up to the square root of the largest output prime. I tried more thoughtful alternatives, and they all slowed down the sieve. Sometimes dumb is beautiful. Thanks to apfelmus for various helpful remarks that lead me to think of this approach. Here is the code: > module BayerPrimes (venturi,primes) where > > -- Code for venturi :: Ord a => [[a]] -> [a] > > merge :: Ord a => [a] -> [a] -> [a] -> [a] > merge xs@(x:xt) ys@(y:yt) zs@(z:zt) > | x <= y = if x <= z > then x : (merge xt ys zs) > else z : (merge xs ys zt) > | otherwise = if y <= z > then y : (merge xs yt zs) > else z : (merge xs ys zt) > merge _ _ _ = undefined > > data List a = A a (List a) | B [a] > > mergeA :: Ord a => List a -> List a -> List a -> List a > mergeA (A x xt) ys zs = A x (mergeA xt ys zs) > mergeA (B xs) ys zs = mergeB xs ys zs > > mergeB :: Ord a => [a] -> List a -> List a -> List a > mergeB xs@(x:xt) ys@(A y yt) zs = case compare x y of > LT -> A x (mergeB xt ys zs) > EQ -> A x (mergeB xt yt zs) > GT -> A y (mergeB xs yt zs) > mergeB xs (B ys) zs = mergeC xs ys zs > mergeB _ _ _ = undefined > > mergeC :: Ord a => [a] -> [a] -> List a -> List a > mergeC xs@(x:xt) ys@(y:yt) zs@(A z zt) > | x < y = if x < z > then A x (mergeC xt ys zs) > else A z (mergeC xs ys zt) > | otherwise = if y < z > then A y (mergeC xs yt zs) > else A z (mergeC xs ys zt) > mergeC xs ys (B zs) = B $ merge xs ys zs > mergeC _ _ _ = undefined > > root :: Ord a => List a -> [List a] -> [a] > root (A x xt) yss = x : (root xt yss) > root (B xs) (ys:zs:yst) = root (mergeB xs ys zs) yst > root _ _ = undefined > > wrap :: [a] -> List a > wrap [] = B [] > wrap (x:xt) = A x $ B xt > > triple :: Ord a => [List a] -> [List a] > triple (x:y:z:xs) = mergeA x y z : (triple xs) > triple _ = undefined > > group :: Ord a => [List a] -> [List a] > group (x:y:xt) = x : y : (group $ triple xt) > group _ = undefined > > venturi :: Ord a => [[a]] -> [a] > venturi (x:xt) = root (wrap x) $ group $ map wrap xt > venturi _ = undefined > > -- Code for primes :: Integral a => [a] > > diff :: Ord a => [a] -> [a] -> [a] > diff xs@(x:xt) ys@(y:yt) = case compare x y of > LT -> x : (diff xt ys) > EQ -> (diff xt yt) > GT -> (diff xs yt) > diff _ _ = undefined > > trim :: Integral a => a -> [a] -> [a] > trim p = let f m x = mod x m /= 0 in filter (f p) > > seed :: Integral a => [a] > seed = [2,3,5,7,11,13,17] > > wheel :: Integral a => [a] > wheel = drop 1 [ m*j + k | j <- [0..], k <- ws ] > where m = foldr1 (*) seed > ws = foldr trim [1..m] seed > > multiples :: Integral a => [a] -> [[a]] > multiples ws = map fst $ tail $ iterate g ([], ws) > where g (_,ps@(p:pt)) = ([ m*p | m <- ps ], trim p pt) > g _ = undefined > > primes :: Integral a => [a] > primes = seed ++ (diff wheel $ venturi $ multiples wheel)

6 8

FGL/Haskell and Hierarchical Clustering/dendograms
by Nikolas Borrel-Jensen 29 Dec '09

29 Dec '09

Hi! I have some trouble implementing single-linkage clustering algorithm by using a minimum-spanning tree, so I would appreciate if some of you could give me some advise. I am implementing a single-linkage clustering algorithm, and my approach is to use minimum spanning trees for that task. I am using the library FGL ( http://web.engr.oregonstate.edu/~erwig/fgl/haskell/) and I have managed to compute a minimum spanning tree from an arbitrary fully connected graph with 5 nodes. I get [ [(4,0) ] , [ (3,1) , (4,0) ] , [ (1,1) , (3,1) , (4,0) ] , [ (2,3) , (4,0) ] , [ (5,12) , (2,3) , (4,0) ] ], which is the root path tree of the minimum spanning tree created by the function msTreeAt. >From that I would create a dendrogram. [ (1,1) , (3,1) , (4,0) ] is telling that node 1,3 and 4 has the same cost, namely cost 1. Therefore these are merged at level 1. At level 1 we now have 3 clusters: (1,3,4), 2 and 5. Now the second lowest should be merged, that is 2 and 4. BUT because 4 is already merged in the cluster (1,3,4), we should merge (1,3,4) and 2 at level 3 (because the cost is 3). Now at level 3 we have 2 clusters, (1,2,3,4) and 5. Now we merge the last one at level 12: (1,2,3,4,5), and we are finished. I have very hard to see, how this could be done efficiently without pointers (as in C). I have thought of just saving the nodes from the start of the root path, and traversing it, but a lot of searching should be done all the time. Can you please give me some advise on that? Kind regards Nikolas Borrel-Jensen Computer Science University Of Copenhagen

3 4

Upgraded to GHC 6.12 and can't find anything
by Gregory Propf 28 Dec '09

28 Dec '09

I finally compiled and installed GHC 6.12 on my Linux system and it seems to be failing to find a lot of things. Notably these import Control.Monad import Control.Monad.State import Control.Monad.Trans import Control.Parallel Worked fine under 6.10. Any clues?

4 4