September 2009 - Haskell-Cafe

How to Create Data Type of memory
by Akshay Dave 06 Sep '09

06 Sep '09

Hi All, I am stuck in converting the transition semantics in Haskell. Please let me know how to define memory data types in Haskell( like we define pointer in C). Prompt help would be greatly appreciated. Sincerely, Akshay _________________________________________________________________ Hotmail® is up to 70% faster. Now good news travels really fast. http://windowslive.com/online/hotmail?ocid=PID23391::T:WLMTAGL:ON:WL:en-US:…

1 0

Record update fusion (or how should I call it?)
by Peter Verswyvelen 06 Sep '09

06 Sep '09

I've seen a couple of package being announced that provide first class labels, and other packages already existed for this (Grapefruit Record, HList, Accessor, ...) Regarding this, I have a question about the performance of multiple composed field updates. Maybe an example. Suppose I have a large record - say WindowDescription - which contains a lot of fields. Suppose I have a couple of default window description values, e.g. defaultWindowDesc, dialogBoxDesc, etc Using accessors it is easy to take such a default value, and "modify" a couple of fields, like: let myWindowDesc = set title "Haskell" . set size (640,480) . set background Blue . set fontFamily Arial $ defaultWindowDesc However, I guess this would make a lot of intermediate WindowDescription copies no (whether the fields are strict or not)? So ideally for performance, all these "updates" should be fused, maybe running inside an ST monad? I'm not sure if any of this is valid, but I would like to understand more about this, so any links and hints are welcome :-) Peter Verswyvelen

3 3

Re: How to customize dyre recompile?
by Will Donnelly 06 Sep '09

06 Sep '09

Hi Andy, I feel that I should offer a disclaimer here: You are misusing Dyre somewhat by attempting to make it handle whole-program recompilation. It is designed to recompile a single configuration file, generally against an installed library form of the application. Some of its code, specifically the part that decides when to recompile, is based almost entirely on this assumption. That aside, you should be able to accomplish your goals like this: 1. Set the 'forceRecomp' parameter (just added in Dyre 0.7.3) to 'False'. This will remove the '-fforce-recomp' flag from GHC's options. 2. Run your executable with the '--force-reconf' flag, which will cause Dyre to always enter the recompilation code. In a test project I just created, this seems to do what you desire. Hope this helps clear things up - Will Donnelly On Sun, Sep 6 2009 at 1:41 PM, Andy Stewart <lazycat.manatee(a)gmail.com> wrote: > > Hi all, > > I use below params for configure dyre: > > rebootParams :: Params Config > rebootParams = defaultParams > {projectName = "Main" > ,realMain = manatee > ,showError = rebootShowError > ,cacheDir = Just $ return "/test/Download/cache/" > ,configDir = Just getCurrentDirectory > } > > There have two version of function `reboot` to reboot Master binary: > > reboot :: IORefObject -> IO () > reboot ioRefObject = do > rs <- rebootGetState ioRefObject > relaunchWithBinaryState rs Nothing > > reboot :: IORefObject -> IO () > reboot ioRefObject = do > output <- customCompile rebootParams > case output of > Just o -> putStrLn o -- output recompile error > Nothing -> do -- otherwise relaunch > rs <- rebootGetState ioRefObject > relaunchWithBinaryState rs Nothing > > Becuase i setup `projectName` with `Main`, so i want `dyre` recompile > NECESSARY module when i change any module in my project. > > In first version of function `reboot`, i just use > `relauncheWithBinaryState`, i found `dyre` just recompile all project when i > modified Main.hs, if i modified any others module in project, `dyre` > won't recompile those modified modules. > > In second version, i use `customCompile` for recompile, but this have > another problem, `customComiple` use `-fforce-recomp` flags to remove > all object files, so function `customComiple` will recompile all modules > in project, and not just recompile NECESSARY modules. > > So how to make `dyre` just recompile NECCESSARY modules whatever i > change any modules in project? > > Maybe add new option "--dyre-reconf-necessary" in `dyre`? > > Thanks! > > -- Andy

2 1

Re: memoization
by John Lato 06 Sep '09

06 Sep '09

I just discovered that changing DiffArray to a plain Array improves performance of my code by almost a factor of 10. Bitten by DiffArray yet again! John -- this is no good, just change DiffArray to Array. > update :: (Char -> [Int]) -> DiffArray Int ModP -> Char -> DiffArray Int ModP > update lookup arr c = arr // (map calc . lookup $ c) > where > calc i = (i, (arr ! i) + (arr ! (i-1)))

2 2

Averting QuickCheck Madness
by Christopher Lane Hinson 06 Sep '09

06 Sep '09

There are some libraries that depend on QuickCheck 2, and others that depend on QuickCheck 1. This can be a problem. AIUI, the Haskell Platform current depends on QC1, but intends to move to QC2 soon. I also know that the cabal mailing list has talked about some kind of private-depends capability to mitigate this kind of thing in the future. However, I don't see how it can possibly be a best practice to depend on QuickCheck from a shipping library. End users never use this, and for users of upstream packages who may compile from source and contribute the occasional (but valuable!) patch, this is nothing but a compile-time problem waiting to happen. (Note that a user who contributes to a library should be encouraged to run test suites, but I'm talking about users of upstream packages.) There are some good ideas discussed on this list last year*, but none of them seem to have been blessed by the community. * http://www.haskell.org/pipermail/haskell-cafe/2008-September/047216.html Friendly, --Lane

2 1

Re: [Haskell-cafe] Trying to reduce memory costs of String duplicates - Oh my god it works
by Günther Schmidt 06 Sep '09

06 Sep '09

Hi Luke, Brian, oh my god it works! I'm just saying it because that's a first! Late last night I had already suspected that laziness might be one of the reasons why the memoization technique showed no effect on memory consumption and after Brian's email that's exactly where I tried again, using Bang Patterns. IT WORKED! The memory consumption is now down by 20 fold! Thank you guys very very much! Günther Am 06.09.2009, 03:24 Uhr, schrieb Brian Sniffen <bts(a)evenmere.org>: > Remember that each string will still be read, so you may still > allocate a great deal of memory and generate a great deal of garbage. > You will just release it before long, rather than hold it for the life > of your program. Remember also that the memoization itself is lazy: > it does no good if you read all the file in, then force the > memoizations along with the computation of interest. > > -Brian > > 2009/9/5 Günther Schmidt <gue.schmidt(a)web.de>: >> Hi Luke, >> >> thanks, this is some very good advice as I find many duplicates in the >> data >> I have to iterate over. >> >> However so far I'm unable to tell wether this actually works or not, I >> tried >> it a couple of times under different settings but it showed to >> difference in >> memory consumption. The same mem peeks as before. >> >> Do you have some code that where you could see a before and after? >> >> Günther >> >> >> Am 05.09.2009, 19:38 Uhr, schrieb Luke Palmer <lrpalmer(a)gmail.com>: >> >>> 2009/9/5 Günther Schmidt <gue.schmidt(a)web.de>: >>>> >>>> Hi all, >>>> >>>> I'm reading in a data of 216k records into a map of Key, Values Pairs, >>>> the >>>> values being strings. >>>> >>>> As it happens out of 216k String values there really are only about >>>> 6.6k >>>> distinct string values, so I could save a lot of RAM if I was able to >>>> "insert" only actually *new* string values into the map and use >>>> references >>>> to (string) values that already are in memory instead. >>>> >>>> Is there a container that would, if I wanted to insert an element, >>>> return >>>> a >>>> pair of either the previously inserted, equal value and the container >>>> unchanged, or the new, previously unknown value and the new container >>>> amended by that element? >>> >>> I believe a memoization of the identity function will do what you want: >>> >>> import qualified Data.MemoCombinators as Memo >>> >>> share = Memo.list Memo.char id >>> >>> Then pass any string through share to make/get a cached version. >>> >>> You might want to limit the scope of share -- eg. put it in a where >>> clause for the function where you're using it -- so that it doesn't >>> eat memory for the lifetime of your program, only for when you need >>> it. >>> >>> Luke >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> > > >

1 0

Re: memoization
by John Lato 06 Sep '09

06 Sep '09

Hello, I agree that your answer is elegant, but it's not an efficient algorithm in any language. How about this, keeping the rest of your code the same? import Data.Array.Diff import Data.IArray update :: (Char -> [Int]) -> DiffArray Int ModP -> Char -> DiffArray Int ModP update lookup arr c = arr // (map calc . lookup $ c) where calc i = (i, (arr ! i) + (arr ! (i-1))) solve line sol = (foldl' (update lookup) iArray line) ! snd (bounds iArray) where iArray = listArray (0, length sol) $ 1 : map (const 0) sol lookup c = map (+1) . findIndices (== c) $ sol I would expect that at least some of the C programs would use the same algorithm. It's not the most efficient Haskell implementation, but on my computer it runs the large dataset in a little under 3 seconds, which is probably good enough. Cheers, John > > Hi, > > I participating in de google code jam this year and I want to try to use > haskell. The following > simple http://code.google.com/codejam/contest/dashboard?c=90101#s=p2 > problem > would have the beautiful haskell solution. > > import Data.MemoTrie > import Data.Char > import Data.Word > import Text.Printf > > newtype ModP = ModP Integer deriving Eq > > p=10000 > > instance Show ModP where > show (ModP x) = printf "%04d" x > > instance Num ModP where > ModP x + ModP y = ModP ((x + y) `mod` p) > fromInteger x = ModP (x `mod` p) > ModP x * ModP y = ModP ((x * y) `mod` p) > abs = undefined > signum = undefined > > solve _ [] = 1::ModP > solve [] _ = 0::ModP > solve (hs:ts) t@(ht:tt) | hs==ht = solve ts tt + solve ts t > | otherwise = solve ts t > > go (run, line) = "Case #"++show run++": "++show (solve line "welcome to code > jam") > > main = interact $ unlines . map go . zip [1..] . tail . lines > > > Which is unfortunately exponential. > > Now in earlier thread I argued for a compiler directive in the lines of {-# > Memoize function -#}, > but this is not possible (it seems to be trivial to implement though). Now I > used memotrie which > runs hopelessly out of memory. I looked at some other haskell solutions, > which were all ugly and > more clumsy compared to simple and concise C code. So it seems to me that > haskell is very nice > and beautiful until your are solving real algorithmic problems when you want > to go back to some > imperative language. > > How would experienced haskellers solve this problem? > > Thanks > -- > View this message in context: http://www.nabble.com/memoization-tp25306687p25306687.html > Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. >

1 0

Don't “accidentallyparallelize”
by Gracjan Polak 06 Sep '09

06 Sep '09

Hi all, In "DEFUN 2009: Multicore Programming in Haskell Now!" (http://donsbot.wordpress.com/2009/09/05/defun-2009-multicore-programming-in…) slide 30 I see: Don't “accidentally parallelize”: – f `par` f + e and that the correct way of achieving parallelism is: – f `par` e `pseq` f + e Actually I don't understand the difference between these two forms. Could any brave soul explain it to me, please? As a bonus question: what is the difference between `seq` and `pseq`? -- Gracjan

5 7

How to customize dyre recompile?
by Andy Stewart 05 Sep '09

05 Sep '09

Hi all, I use below params for configure dyre: rebootParams :: Params Config rebootParams = defaultParams {projectName = "Main" ,realMain = manatee ,showError = rebootShowError ,cacheDir = Just $ return "/test/Download/cache/" ,configDir = Just getCurrentDirectory } There have two version of function `reboot` to reboot Master binary: reboot :: IORefObject -> IO () reboot ioRefObject = do rs <- rebootGetState ioRefObject relaunchWithBinaryState rs Nothing reboot :: IORefObject -> IO () reboot ioRefObject = do output <- customCompile rebootParams case output of Just o -> putStrLn o -- output recompile error Nothing -> do -- otherwise relaunch rs <- rebootGetState ioRefObject relaunchWithBinaryState rs Nothing Becuase i setup `projectName` with `Main`, so i want `dyre` recompile NECESSARY module when i change any module in my project. In first version of function `reboot`, i just use `relauncheWithBinaryState`, i found `dyre` just recompile all project when i modified Main.hs, if i modified any others module in project, `dyre` won't recompile those modified modules. In second version, i use `customCompile` for recompile, but this have another problem, `customComiple` use `-fforce-recomp` flags to remove all object files, so function `customComiple` will recompile all modules in project, and not just recompile NECESSARY modules. So how to make `dyre` just recompile NECCESSARY modules whatever i change any modules in project? Maybe add new option "--dyre-reconf-necessary" in `dyre`? Thanks! -- Andy

1 0

ANN: vty-4.0.0.1 released
by Corey O'Connor 05 Sep '09

05 Sep '09

Vty is a terminal UI library. Release 4.0.0.1 brings a number of important fixes, features, and performance enhancements. - Completely rewritten output backend. - Efficient, "scanline rasterization" style output span generator. Has not been fully optimized, but should be fast enough. - Terminfo based display terminal implementation. With specialized derivitives for xterm, Terminal.app, and iTerm.app. - Attempts to robustly handle even terminals that don't support all display attributes. - I've tested the following terminals with success: iTerm.app, Terminal.app, xterm, rxvt, mlterm, Eterm, gnome-terminal, konsole, screen, linux vty. Hopefully you will be as successfull. - Improved unicode support. Double wide characters will display as expected. - 256 color support. See Graphics.Vty.Attributes.Color240. The actual output color is adjusted according to the number of colors the terminal supports. - The Graphics.Vty.Image combinators no longer require matching dimensions to arguments! Unspecified areas are filled in with a user-customizable background pattern. See Graphics.Vty.Picture. - output picture will be cropped to display size as expected. - GHC 6.8 support is broken :-( - Unknown Windows platform support. - API changes: - "getSize" has been removed. Use "terminal vty >>= display_bounds" where "vty" is an instance of the Vty data structure. - added a "terminal" field to the Vty data structure. Accesses the TerminalHandle associated with the Vty instance. See Graphics.Vty.Terminal for details on the API usable with a TerminalHandle. - Graphics.Vty.Types has undergone a number of changes. Summary: - Partitioned into Graphics.Vty.Attributes for display attributes. Graphics.Vty.Image for image combinators. Graphics.Vty.Picture for final picture construction. - Graphics.Vty.Attributes: - "setFG" and "setBG" are now "with_fore_color" and "with_back_color" - All other "set.." equations similarly replaced. - "attr" is now "def_attr", short for "default display attributes" Also added a "current_attr" for "currently applied display attributes" - Graphics.Vty.Image: - "horzcat" is now "horiz_cat" - "vertcat" is now "vert_cat" - "renderBS" is now "utf8_bytestring" - "renderChar" is now "char" - "renderFill" is now "char_fill" - added a "utf8_string" and "string" (AKA "iso_10464_string") for UTF-8 encoded Strings and ISO-10464 encoded Strings. String literals in GHC have an ISO-10464 runtime representation. - Graphics.Vty.Picture: - exports Graphics.Vty.Image - "pic" is now "pic_for_image" - added API for setting background fill pattern. issues resolved: - "gnome terminal displays non-basic attributes as strikethrough" - http://trac.haskell.org/vty/ticket/14 - "Multi-byte characters are not displayed correctly on update" - http://trac.haskell.org/vty/ticket/10 - "Redraw does not handle rendering a line that extends beyond screen width characters" - http://trac.haskell.org/vty/ticket/13 - "The <|> and <-> combinators should be more forgiving of mismatched dimensions" - http://trac.haskell.org/vty/ticket/9 - "256-color support" - http://trac.haskell.org/vty/ticket/19

2 2