January 2012 - Haskell-Cafe

Finding longest common prefixes in a list
by Gwern Branwen 24 Jan '12

24 Jan '12

Recently I wanted to sort through a large folder of varied files and figure out what is a 'natural' folder to split out, where natural means something like >4 files with the same prefix. (This might be author, genre, subject, whatever I felt was important when I was naming the file.) Now usually I name files with hyphens as the delimiters like the hypothetical '1998-wadler-monads.pdf', and it would be easy to write a stdin/stdout filter to break Strings on hyphens and sort by whatever is most common. But this is rather hardwired, can I solve the more general problem of finding the longest common prefixes, whatever they are? This turns out to be much more difficult than simply finding 'the' longest common prefix (which is usually ""). I found an algorithm of sorts at http://stackoverflow.com/a/6634624 but it was easier described than implemented. Eventually I wrote what I *think* is a correct program, but it's definitely of the write-only sort. Perhaps people have better implementations somewhere? I saw a lot of discussion of tries, but I didn't go that route. The code, followed by an example: #!/usr/bin/env runhaskell import Data.List (intercalate, isPrefixOf, nub, sort) main :: IO () main = interact (unlines . intercalate [""] . chunkFiles . lines ) -- basic algorithm from <http://stackoverflow.com/a/6634624> chunkFiles :: Ord a => [[a]] -> [[[a]]] chunkFiles f = map (\(_,b) -> filter (isPrefixOf b) f) $ sort $ map (\x -> (countPrefixes x f,x)) (e $ bar f) sharedPrefixes :: Ord a => [[a]] -> [a] sharedPrefixes [] = [] sharedPrefixes s = foldr1 sp2 s where sp2 l1 l2 = map fst . takeWhile (uncurry (==)) $ zip l1 l2 traverse :: Ord a => [[a]] -> [[a]] traverse [] = [] traverse x = sharedPrefixes (take 2 x) : traverse (drop 1 x) bar :: Ord a => [[a]] -> [[a]] bar = nub . sort . traverse . sort countPrefixes :: (Ord a) => [a] -> [[a]] -> Int countPrefixes x xs = length $ filter (x `isPrefixOf`) xs e :: Eq a => [[a]] -> [[a]] e y = map fst $ filter snd $ map (\x -> (x, (==) 1 $ length . filter id $ map (x `isPrefixOf`) y)) y {- Example input from `ls`: chorus-kiminoshiranaimonogatari.ogg chorus-mrmusic.ogg choucho-lastnightgoodnight.ogg dylanislame-aikotoba.ogg electriclove-エレクトリック・ラブ-korskremix.ogg gumi-bacon8-justhangingaround.ogg gumi-iapologizetoyou.ogg gumi-montblanc.ogg gumi-mozaikrole.ogg gumi-ハッピーシンセサイザ.ogg gumi-showasengirl.ogg gumi-sweetfloatflatsスイートフロートアパート.ogg gumi-timewarpedafterchoppingmystagbeetle.ogg gumi-オリジナル曲-付きホシメグリ.ogg gumi-ミクオリジナル親友.ogg kaito-byakkoyano.ogg kaito-flowertail.ogg kasaneteto-tam-ochamekinou重音テト吹っ切れたおちゃめ機能.ogg len-crime-timetosaygoodbye.ogg len-fire◎flower.ogg len-ponponpon.ogg lily-prototype.ogg luka-apolxcore-waitingforyou.ogg luka-dimトロイ.ogg luka-dion-myheartwillgoon.ogg luka-dirgefilozofio-dirgeasleepinjesus.ogg luka-アゴアニキ-doubelariatダブルラリアット.ogg luka-emon-heartbeats.ogg luka-emonloid3-ハローハロー.ogg luka-everybreathyoutake.ogg luka-オリジナル-garden.ogg luka-justbefriends.ogg lukameiko-gemini.ogg luka-milkyway.ogg luka-やみくろ-かいぎ.ogg luka-tic-tick.ogg luka-torinouta.ogg luka-zeijakukei-shounenshoujo.ogg luka-勝手にアニメ-nologic-作ってみた.ogg luka-駄目人間.ogg meiko-artemis-awake.ogg miku-9ronicleプラチナ.ogg miku-acolorlinkingworld-この世界の下で.ogg miku-acolorlinkingworld-青い花.ogg miku-a+jugos-lullabyforkindness.ogg miku-akayaka-beacon.ogg miku-akayakap-sunrise.ogg miku-aoihana.ogg miku-arabianresponse.ogg miku-avtechno-tear.ogg miku-こえをきかせてcicci.ogg miku-cleantears-remind2011natsu-greenhillzonecrystiararemix.ogg miku-cleantears-remind2011natsu-夏影summerwindremix.ogg miku-clocklockworks.ogg miku-dancedancevol2-runner.ogg miku-daniwellp-chaoticuniverse.ogg miku-dixieflatline-shinonomescrumble.ogg miku-electricloveエレクトリックラヴ.ogg miku-elegumitokyo-kissmebaby.ogg miku-galaxyodyssey-cryingirl.ogg miku-galaxyodyssey-galaxyspacelines.ogg miku-hakamairi.ogg miku-haruna.ogg miku-heartshooter.ogg miku-hoshikuzutokakera.ogg miku-innes.ogg miku-innocence初音ミク.ogg miku-jemappelle-motion-likeyou.ogg miku-jemappelle-motion-ohwell.ogg miku-jevannip-myfavoritesummer.ogg miku-kakokyuudance-過呼吸ダンス.ogg miku-kz-packaged.ogg miku-kz-tellyourworld.ogg miku-lastscene.ogg miku-lostmemories付き-初音ミク.ogg miku-lovelyday.ogg miku-いいわけlove_song.ogg mikulukagumi-prayfor.ogg miku-maple-初音ミク楓-オリジナル曲.ogg miku-more1.5.ogg miku-m(a)rk-eklosion.ogg miku-m(a)rk-kirch.ogg miku-nana-ボーナストラック-ハッピー般若コア.ogg miku-nekomimiswitch.ogg miku-nightrainbow.ogg miku-noyounome.ogg miku-むかしむかしのきょうのぼくオリジナル.ogg miku-pandolistp-neverendinghammertime.ogg miku-ジラートP-birthdayofeden-deepsleep.ogg miku-ジラートP-birthdayofeden-水中読書.ogg miku-plustellia-dear.ogg miku-plustellia-壁の彩度-crazygirl.ogg miku-plustellia-壁の彩度-discoradio.ogg miku-ぽわぽわP-ストロボライト.ogg miku-rabbitforgets.ogg miku-re:package-lastnightgoodnight.ogg miku-re:package-ourmusic.ogg miku-re:package-sutorobonaitsu.ogg miku-rollinggirl.ogg miku-ryo-メルト-melt.ogg miku-senseiniitteyaro.ogg miku-sevencolors-レモネード.ogg miku-shoukinosatadenia.ogg miku-stratosphere.ogg miku-supernova.ogg miku-tam-lastnightgoodnight.ogg miku-tanatofobia.ogg miku-thearmyforyourenvy-スーパー・ノヴァ.ogg miku-theendlesslove.ogg miku-tinyparadise-snowflake.ogg miku-tinyparadise-tinyparadise.ogg miku-unfragment.ogg miku-worldismine-ルドイズマイン.ogg miku-yakiimo.ogg miku-文学少年の憂鬱-オリジナル.ogg miku-カラフルポップビートオリジナル曲.ogg miku-杯本選life.ogg miku-杯本選初音ミクどういうことなのダンス.ogg miku-般若心経beautyfloor-buddhamix.ogg miku-般若心経ポップ.ogg niconicochorus-blackrockshooter.ogg niconicochorus-justbefriends.ogg rin-dixieflatline-gemini.ogg rin-elegumitokyo-二人、恋してgirlsside.ogg rin-helloworld.ogg rin-jutenija.ogg rin-lastnightgoodnight.ogg rin-ripples-evergreen.ogg rin-っ´ω｀c.ogg rollinggirl-piano.ogg seeu-gagain-따라리라ddadada.ogg utau-雪歌ユフbeyondオリジナル曲.ogg yuki-discochocolatheque.ogg yuki-shouwasenhosiga^ru.ogg yuki-shouwasenhosiga^ru.ogg Example output from `ls | ~/lcp.hs`: chorus-kiminoshiranaimonogatari.ogg chorus-mrmusic.ogg gumi-montblanc.ogg gumi-mozaikrole.ogg gumi-showasengirl.ogg gumi-sweetfloatflatsスイートフロートアパート.ogg kaito-byakkoyano.ogg kaito-flowertail.ogg luka-emon-heartbeats.ogg luka-emonloid3-ハローハロー.ogg luka-tic-tick.ogg luka-torinouta.ogg miku-acolorlinkingworld-この世界の下で.ogg miku-acolorlinkingworld-青い花.ogg miku-akayaka-beacon.ogg miku-akayakap-sunrise.ogg miku-cleantears-remind2011natsu-greenhillzonecrystiararemix.ogg miku-cleantears-remind2011natsu-夏影summerwindremix.ogg miku-dancedancevol2-runner.ogg miku-daniwellp-chaoticuniverse.ogg miku-electricloveエレクトリックラヴ.ogg miku-elegumitokyo-kissmebaby.ogg miku-galaxyodyssey-cryingirl.ogg miku-galaxyodyssey-galaxyspacelines.ogg miku-hakamairi.ogg miku-haruna.ogg miku-innes.ogg miku-innocence初音ミク.ogg miku-jemappelle-motion-likeyou.ogg miku-jemappelle-motion-ohwell.ogg miku-kz-packaged.ogg miku-kz-tellyourworld.ogg miku-lostmemories付き-初音ミク.ogg miku-lovelyday.ogg miku-m(a)rk-eklosion.ogg miku-m(a)rk-kirch.ogg miku-plustellia-壁の彩度-crazygirl.ogg miku-plustellia-壁の彩度-discoradio.ogg miku-senseiniitteyaro.ogg miku-sevencolors-レモネード.ogg miku-tam-lastnightgoodnight.ogg miku-tanatofobia.ogg miku-thearmyforyourenvy-スーパー・ノヴァ.ogg miku-theendlesslove.ogg miku-tinyparadise-snowflake.ogg miku-tinyparadise-tinyparadise.ogg miku-ジラートP-birthdayofeden-deepsleep.ogg miku-ジラートP-birthdayofeden-水中読書.ogg miku-杯本選life.ogg miku-杯本選初音ミクどういうことなのダンス.ogg miku-般若心経beautyfloor-buddhamix.ogg miku-般若心経ポップ.ogg niconicochorus-blackrockshooter.ogg niconicochorus-justbefriends.ogg len-crime-timetosaygoodbye.ogg len-fire◎flower.ogg len-ponponpon.ogg luka-dimトロイ.ogg luka-dion-myheartwillgoon.ogg luka-dirgefilozofio-dirgeasleepinjesus.ogg miku-re:package-lastnightgoodnight.ogg miku-re:package-ourmusic.ogg miku-re:package-sutorobonaitsu.ogg miku-nana-ボーナストラック-ハッピー般若コア.ogg miku-nekomimiswitch.ogg miku-nightrainbow.ogg miku-noyounome.ogg rin-dixieflatline-gemini.ogg rin-elegumitokyo-二人、恋してgirlsside.ogg rin-helloworld.ogg rin-jutenija.ogg rin-lastnightgoodnight.ogg rin-ripples-evergreen.ogg rin-っ´ω｀c.ogg -} -- gwern http://www.gwern.net

2 4

Monads, do and strictness
by Victor S. Miller 23 Jan '12

23 Jan '12

The "do" notation translates do {x <- a;f} into a>>=(\x -> f) However when we're working in the IO monad the semantics we want requires that the lambda expression be strict in its argument. So is this a special case for IO? If I wanted this behavior in other monads is there a way to specify that? Victor Sent from my iPhone

9 23

ANN: OpenCL 1.0.3.0 package
by Luis Cabellos 23 Jan '12

23 Jan '12

Hello, I update the OpenCL package with the last changes. The most important thing, currently it fully implements OpenCL 1.0. IMPORTANT, some functions change signature (e,g: clSetKernelArg, and clCreateContext* ) Thanks all comments in the previous version, issues and pulls in github. # Where to get it * Hackage page (http://hackage.haskell.org/package/OpenCL) * Repository (https://github.com/zhensydow/opencl) * Bugs (https://github.com/zhensydow/opencl/issues) # Changes * Move to Control.Parallel.OpenCL (thanks Jason Dagit) * Added Image functions * Added clExecuteNativeKernel * Fixes on Windows, Macos and Linux versions (thanks Anthony Cowley, ehird, axman6) * Fix bug with preprocessor code in OpenCL source code * Fix clSetKernelArg to allow cannot specify size of local memory arrays Thanks, Luis Cabellos

1 0

Can't install hspec
by Erik de Castro Lopo 23 Jan '12

23 Jan '12

Hi all, I'm trying to cabal install hspec and I get the following: Resolving dependencies... /tmp/hspec-0.9.04062/hspec-0.9.0/Setup.lhs:2:10: Could not find module `System' It is a member of the hidden package `haskell98-2.0.0.0'. Use -v to see a list of the files searched for. cabal: Error: some packages failed to install: hspec-0.9.0 failed during the configure step. The exception was: ExitFailure 1 This is with ghc-7.2.2. Any clues how I can get around this? Cheers, Erik -- ---------------------------------------------------------------------- Erik de Castro Lopo http://www.mega-nerd.com/

2 1

Idris
by Ryan Ingram 23 Jan '12

23 Jan '12

Has anyone played with Idris (http://idris-lang.org/) at all? It looks interesting, and I'd love to play with it, but unfortunately I only have windows machines up and running at the moment and the documentation seems to imply it only builds on unixy systems. I'm curious how difficult it would be to get a win32 implementation up and running. -- ryan

3 2

Compiling dph package with ghc-7.4.0.20111219
by mukesh tiwari 23 Jan '12

23 Jan '12

Hello all I have installed ghc-7.4.0.20111219 and this announcement<http://www.haskell.org/pipermail/glasgow-haskell-users/2011-December/021310…>says that "The release candidate accidentally includes the random, primitive, vector and dph libraries. The final release will not include them". I tried to compile a program [ntro@localhost src]$ ghc-7.4.0.20111219 -c -Odph -fdph-par ParallelMat.hs ghc: unrecognised flags: -fdph-par Usage: For basic information, try the `--help' option. [ntro@localhost src]$ ghc-7.2.1 -c -Odph -fdph-par ParallelMat.hs Also in ghc-7.4.0.20111219 --help , i don't see any option related data parallel haskell. I search the ghc manual <http://www.haskell.org/ghc/dist/stable/docs/html/users_guide/> and got one reference for data parallel haskell<http://www.haskell.org/ghc/dist/stable/docs/html/users_guide/lang-parallel.…>. This link again redirects to data parallel haskell <http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell> wiki page using ghc-7.2.1. Could some one please tell me how to compile haskell program using dph with ghc-7.4.0.20111219. Regards Mukesh Tiwari

4 6

Right tree structure for complicated problem
by Pierre Penninckx 22 Jan '12

22 Jan '12

Hello everyone, So here is what I want to achieve: I'd like a program that calculates the time needed for water to flow out of a circuit made out of tube. The rules are : - There are multiple sources of water and only one exit. - The water can only take one path from a source to the exit. - Of course, a source of water contains a certain amount of water at the beginning. ### Algorithm Here's the concept of how it should be working: #1 The tubes are connected together : 1 parent with n childs. This looks really like a tree: data Tree = Leaf { getVolume::Int } | Path { getMaxFlow::Int , getFlow::Int , getOpen::Bool , getChilds::[Tree} } But this structure doesn't work well :( (see later why) When I determine the time taken by the water to flow down to the exit, I need to take water jams (haha) into account. To do this, the algorithm begins by the exit node and "distribute" it's maximum flow through the childs, but only to open tubes. And the childs distribute their flow to their own child. Repeat until you reach a Leaf. example : Path 5 0 True [Path 4 0 True [], Path 3 0 True [], Path 3 0 False []] after distribution: Path 5 5 True [Path 4 4 True [], Path 3 2 True [], Path 3 0 False []] #2 After the distribution, you must get the water out. Easy, the time taken by the water to flow down is, in pseudo code: max( for all leafs : getVolume * getFlow ) ### Problem My problem, is this : I must be able to change the "distribution" the flow of the parent to its childs: in my example, I said "take the biggest child, give it all you can and give the rest to the other childs, repeat" but I could have said "give first to the lowest child" or "give a certain percentage depending of the sum of the childs max capacity" So I can't map simply over the childs: distribute :: (Int -> Int -> Int) -> Tree -> Tree distribute _ (Leaf a) = Leaf a distribute f path@(Path _ _ False _) = path distribute f (Path max cur open childs) = Path max (f cur) open (map f childs) I must indeed let the distribution function choose to which childs it wants to give: distribute :: (Int -> [Tree] -> [Tree]) -> Tree -> Tree distribute f (Path max use open child) = Path max use open $ map (distribute (f use)) newChilds where newChilds = f use childs And I find this quite awful... I know Hakell is everything about data structure, so I suppose my data structure is awful too. Do you have any suggestions/remarks to help me? Sorry I made it so long, but you needed to know what I wanted to acheive to help me (I hope I made it crystal clear ^^). Thanks, Ibiz

2 2

GLFW-0.5.0.0 is released
by Paul Liu 22 Jan '12

22 Jan '12

There is now a new GLFW package on hackage with version number 0.5.0.0. Maintainers of packages that depend on GLFW may want to update your packages since (1) GLFW-0.4.2 is mostly broken on OS X Lion (10.7); (2) there are incompatible API changes. Notable changes include (but not limited to): 1. It now uses GLFW C library version 2.7.2 on all platforms. 2. It still tries to compile and build a static version of the C library on all platforms. If this is not what you want, use '--flags dynamic' to dynamically link to pre-installed glfw C library on your system. 3. It nows does a much better job at configuring itself on Linux and FreeBSD. 4. There is an outstanding bug preventing GLFW programs to be invoked from GHCi on OS X. One has to compile before running GLFW programs. 5. Documentation has been improved, and there are also API changes affecting window params and hints. See the hackage documentation for details. 6. An example program and detail change log are included if you unpack the source. Many thanks to Marc Sunet and a lot of other people for sending in bug reports and helping out with this upgrade. Marc is now also a maintainer of this package. Please send your bug report to either of us or to the GLFW mailing list <glfw(a)projects.haskell.org>. For new users to GLFW or GLFW-b, there are some style and API differences between these two packages (see https://github.com/bsl/GLFW-b/blob/master/README.md) and in particular, GLFW includes some basic texture support and a "quick-and-dirty" font rendering hack (not found in GLFW C library). Now, more on the outstanding bug with GHCi on OS X. Here is what happens when invoking initialize from GHCi on OS X: Prelude> import Graphics.UI.GLFW Prelude Graphics.UI.GLFW> initialize Loading package OpenGLRaw-1.1.0.1 ... linking ... done. Loading package GLURaw-1.1.0.0 ... linking ... done. Loading package ObjectName-1.0.0.0 ... linking ... done. Loading package StateVar-1.0.0.0 ... linking ... done. Loading package Tensor-1.0.0.1 ... linking ... done. Loading package OpenGL-2.4.0.1 ... linking ... done. Loading package GLFW-0.5.0.0 ... linking ... done. objc[18039]: Object 0x105e00a70 of class __NSCFString autoreleased with no pool in place - just leaking - break on objc_autoreleaseNoPool() to debug 2012-01-21 03:23:58.574 ghc[18039:1303] -[NSAutoreleasePool init]: unrecognized selector sent to instance 0x105e00740 2012-01-21 03:23:58.577 ghc[18039:1303] *** Terminating app due to uncaught exception 'NSInvalidArgumentException', reason: '-[NSAutoreleasePool init]: unrecognized selector sent to instance 0x105e00740' On the other hand, if GLFW is installed with the dynamic flag to link to a pre-installed system libglfw.dylib, then initialize would work fine but again GLFW applications still fail to run properly as the window fails to receive user input and seems to hang. The enableGUI hack wouldn't help either (and is broken on 10.7). I believe this situation is the same when running GLFW-b applications from GHCi on OS X, since it builds and installs dynamic library on OS X too. Compiled applications are not affected by this bug. Any help is greatly appreciated! Thanks! -- Regards, Paul Liu

2 2

Re: [Haskell-cafe] Fwd: Monads, do and strictness
by David Barbour 21 Jan '12

21 Jan '12

On Sat, Jan 21, 2012 at 2:24 PM, Roman Cheplyaka <roma(a)ro-che.info> wrote: > * David Barbour <dmbarbour(a)gmail.com> [2012-01-21 12:18:09-0800] > > `undefined` is not a value in any domain. It isn't a value at all. It's > > certainly not part of my monad language or algebra. Up to the semantic > > level of comparing observable and legally defined behaviors, we can have > > the identity law. That's sufficient for the letter of the law, even if > not > > ideal from Haskell's operational perspective. > > First, can we please agree on what kind of semantics we are discussing? > > In the beginning you are talking about domains, so it sounds like > denotational semantics. But then you move to behaviours, and that sounds > like operational semantics. > Can you first agree what *layer* of semantics you are discussing? It's useful to understand programs in layers. Your argument seems to depend on confusing the semantics of the monad abstraction with the semantics of the Haskell representation of the abstraction. We could even look at underlying layers, such as the implementation of Haskell - including allocation and GC. The important point is that the ONLY relevant layer for monad laws is the monad algebra itself - not the representation in Haskell, and certainly not the representation of Haskell on a Von Neumann machine. Since strictness does not affect the *values* of any elements in the monad's algebra, it is trivial to meet the monad laws. My argument did switch from denotational to operational as I crossed layers, but that was a conscious decision on my part. > If we are talking about the denotational semantics, then we choose a > domain and need to map every legal Haskell expression to something in > that domain. > We can discuss denotational semantics of many languages. And we can discuss the representations of those languages in Haskell. And we can discuss the denotational semantics of Haskell. Layers upon layers. Denotational semantics certainly doesn't imply the Haskell layer. Regards, Dave

1 0

Fwd: Monads, do and strictness
by David Barbour 21 Jan '12

21 Jan '12

`undefined` is not a value in any domain. It isn't a value at all. It's certainly not part of my monad language or algebra. Up to the semantic level of comparing observable and legally defined behaviors, we can have the identity law. That's sufficient for the letter of the law, even if not ideal from Haskell's operational perspective. Implicit use of laziness or undefined to model and reason about data or algebras is a mistake that mixes semantic layers. Even in Haskell. There's a reason every robust library for processing signals or streams will model them explicitly. Regards, Dave On Sat, Jan 21, 2012 at 11:22 AM, Roman Cheplyaka <roma(a)ro-che.info> wrote: > * David Barbour <dmbarbour(a)gmail.com> [2012-01-21 11:09:43-0800] > > Logically only has meaning when `=` applies to values in the domain. > > `undefined` is not a value in the domain. > > > > We can define monads - which meet monad laws - even in strict languages. > > In strict languages 'undefined' is not a value in the domain indeed, but > it is in non-strict languages, exactly because they are non-strict. > > I think that's what Robert Harper meant by saying that Haskell doesn't > have a type of lists, while ML has one [1]. > > [1]: > http://existentialtype.wordpress.com/2011/04/24/the-real-point-of-laziness/ > > -- > Roman I. Cheplyaka :: http://ro-che.info/ >

2 1