April 2009 - Haskell-Cafe

History data structure suggestion
by Victor Nazarov 12 Apr '09

12 Apr '09

Hello, I have a gtk2hs application. I'd like to implement some kind of browser history for it. It should have Back and Forward buttons and a popup menu with radio items.History is a list of strings. There is a current position in this list, so you can move this position back and forward. Some kind of list zipper must be enough to implement this: data History a = Empty | Hist { histBefore :: [a], histCurrent :: a, histAfter :: [a] } back, forward:: History a -> History a back (Hist (b:bs) c as) = Hist bs b (c:as) forward (Hist bs c (a:as)) = Hist (c:bs) a as add :: a -> History a -> History a add x (Hist bs c _) = Hist (c:bs) x [] --- When you add something, future part of history becomes blank. add x Empty = Hist [] x [] start :: History a -> History a start (Hist bs c as) = Hist [] h (hs ++ [c] ++ as) where (h:hs) = reverse bs But there is another requirement. There must be some "points" in the history to store in popup menu. When you select any point the history sould be rolled to this point. For example. data HistPoint a = HP Int current :: History a -> HistPoint a current (Hist bs _ _) = HP (length bs) goTo :: HistPoint a -> History a -> History a goTo (HP n) = foldr1 (.) (replicate n forward) . start I wonder is there more effective, more easy to implement data structure to represent History and HistPoint -- Victor Nazarov

2 1

Re: [Haskell-cafe] Functions that return functions
by michael rice 12 Apr '09

12 Apr '09

You're getting ahead of me again. Michael --- On Sun, 4/12/09, Jake McArthur <jake.mcarthur(a)gmail.com> wrote: From: Jake McArthur <jake.mcarthur(a)gmail.com> Subject: Re: [Haskell-cafe] Functions that return functions To: "michael rice" <nowgate(a)yahoo.com> Cc: haskell-cafe(a)haskell.org Date: Sunday, April 12, 2009, 5:45 PM michael rice wrote: > Admittedly, functions that return functions are Lispy, but perhaps there a Haskelly way to accomplish the same thing? Actually, I think you will come to find that this way of thinking is more Haskelly than it is Lispy! import Control.Applicative ((<$), (<*>)) import Control.Arrow ((&&&)) import Control.Monad (guard) import Data.List (unfoldr) makeVerifier f m = (==0) . (`mod` m) . sum . zipWith f [1..] . unfoldr nextDigit where nextDigit = (<$) . (snd &&& fst) . (`divMod` 10) <*> guard . (/= 0) - Jake

2 1

Re: [Haskell-cafe] Functions that return functions
by michael rice 12 Apr '09

12 Apr '09

Thanks, guys! Boy, this bunch of complemented partially applied functions gives a whole new meaning to the term "thinking ahead." And the whole shebang is waiting on that input integer to set everything in motion. Pretty clever. To generalize, I changed the function to: makeVerifier :: ((Int,Int) -> Int) -> Int -> (Int -> Bool) makeVerifier f m = divides m . foldl (+) 0 . map f . zip [1 .. ] . digits so, in Haskell let checkIsbn = makeVerifier (\ (i,d) -> i * d) 11 let checkUpc = makeVerifier (\ (i,d) -> if odd i then d else 3*d) 10 let checkCc = makeVerifier (\ (i,d) -> if odd i then d else if d < 5 then 2*d else 2*d+1) 10 let checkUsps = makeVerifier (\ (i,d) -> if i == 1 then -d else d) 9 I think I'm catching on. Michael --- On Sun, 4/12/09, Daniel Fischer <daniel.is.fischer(a)web.de> wrote: From: Daniel Fischer <daniel.is.fischer(a)web.de> Subject: Re: [Haskell-cafe] Functions that return functions To: haskell-cafe(a)haskell.org Cc: "michael rice" <nowgate(a)yahoo.com> Date: Sunday, April 12, 2009, 12:15 PM Am Sonntag 12 April 2009 17:38:53 schrieb michael rice: > The following are exercises 5.10, and 5.11 from the Scheme text "Concrete > Abstractions" by Max Hailperin, et al. The text at that point is about > writing verifiers to check ID numbers such as ISBNs, credit card numbers, > UPCs, etc. > > ====== > > Exercise 5.10 > Write a predicate that takes a number and determines whether the sum of its > digits is divisible by 17. > > Exercise 5.11 > Write a procedure make-verifier, which takes f and m as its two arguments > and returns a procedure capable of checking a number. The argument f is > itself a procedure of course. Here is a particularly simple example of a > verifier being made and used. > > (define check-isbn (make-verifier * 11)) > > (check-isbn 0262010771) > #t > > The value #t is the "true" value; it indicates that the number is a valid > ISBN. > > As we just saw, for ISBN numbers the divisor is 11 and the function is > simply f(i,d(i)) = i * d(i). Other kinds of numbers use slightly more > complicated functions, but you will still be able to use make-verifier to > make a verifier much more easily than if you had to start from scratch. > > ======= > > Here's the Scheme check-verifier function I wrote, followed by my humble > attempt at a Haskell function that does the same thing. Below that are some > verifier functions created with the Scheme make-verifier. Admittedly, > functions that return functions are Lispy, but perhaps there a Haskelly way > to accomplish the same thing? Functions returning functions are quite natural in Haskell. Since usually functions are written in curried form, a function returng a function corresponds to a function of multiple arguments applied to only some of them. > > Michael > > =============== > > > (define (make-verifier f m) ;f is f(i,d) & m is divisor > (lambda (n) > (let* ((d (digits n)) > (i (index (length d)))) ;(index 3) => (1 2 3) > (divides? m (reduce + 0 (map f i d)))))) #f > > makeVerifier :: (Int -> Int -> Int) -> Int -> (Int -> Bool) > > makeVerifier f m = \n -> let d = digits n > > i = [1..(length d)] > > in \n -> divides m (foldl (+) 0 (map2 f i d)) > > makeVerifier f m n = divides m . foldl (+) 0 $ zipWith f [1 .. ] (digits n) just call makeVerifier f m to get your verification function :) If you don't want to name the last argument: makeVerifier f m = divides m . foldl (+) 0 . zipWith f [1 .. ] . digits more point-freeing would be obfuscation. Instead of foldl (+) 0, you could also just write sum. > > -- Note: Reduce is just foldl f 0 lst, but map2 is > map2 :: (Int -> Int -> Int) -> [Int] -> [Int] -> [Int] > map2 f m n = [ f i d | (i,d) <- zip m n] map2 is zipWith, already in the Prelude. > > -- And here's my digits function > digits :: Int -> [Int] > digits 0 = [] > digits n = rem n 10 : digits (quot n 10) Unless you are desperate for speed and sure you deal only with positive numbers (or know that you really want quot and rem), better use div and mod. Those give the commonly expected (unless your expectation has been ruined by the behaviour of % in C, Java...) results. > > -- And divides function > divides :: Int -> Int -> Bool > divides divisor n = 0 == rem n divisor > > ===== > > (define check-isbn ;book number > (make-verifier > * > 11)) > > (define check-upc ;universal product code > (make-verifier > (lambda (i d) (if (odd? i) d (* 3 d))) > 10)) > > (define check-cc ;credit card > (make-verifier > (lambda (i d) (if (odd? i) d (if (< d 5) (* 2 d) (+ (* 2 d) 1)))) > 10)) > > (define check-usps ;postal money order > (make-verifier > (lambda (i d) (if (= i 1) (- d) d)) > 9))

2 1

Functions that return functions
by michael rice 12 Apr '09

12 Apr '09

The following are exercises 5.10, and 5.11 from the Scheme text "Concrete Abstractions" by Max Hailperin, et al. The text at that point is about writing verifiers to check ID numbers such as ISBNs, credit card numbers, UPCs, etc. ====== Exercise 5.10 Write a predicate that takes a number and determines whether the sum of its digits is divisible by 17. Exercise 5.11 Write a procedure make-verifier, which takes f and m as its two arguments and returns a procedure capable of checking a number. The argument f is itself a procedure of course. Here is a particularly simple example of a verifier being made and used. (define check-isbn (make-verifier * 11)) (check-isbn 0262010771) #t The value #t is the "true" value; it indicates that the number is a valid ISBN. As we just saw, for ISBN numbers the divisor is 11 and the function is simply f(i,d(i)) = i * d(i). Other kinds of numbers use slightly more complicated functions, but you will still be able to use make-verifier to make a verifier much more easily than if you had to start from scratch. ======= Here's the Scheme check-verifier function I wrote, followed by my humble attempt at a Haskell function that does the same thing. Below that are some verifier functions created with the Scheme make-verifier. Admittedly, functions that return functions are Lispy, but perhaps there a Haskelly way to accomplish the same thing? Michael =============== (define (make-verifier f m) ;f is f(i,d) & m is divisor (lambda (n) (let* ((d (digits n)) (i (index (length d)))) ;(index 3) => (1 2 3) (divides? m (reduce + 0 (map f i d)))))) #f makeVerifier :: (Int -> Int -> Int) -> Int -> (Int -> Bool) makeVerifier f m = \n -> let d = digits n i = [1..(length d)] in \n -> divides m (foldl (+) 0 (map2 f i d)) -- Note: Reduce is just foldl f 0 lst, but map2 is map2 :: (Int -> Int -> Int) -> [Int] -> [Int] -> [Int] map2 f m n = [ f i d | (i,d) <- zip m n] -- And here's my digits function digits :: Int -> [Int] digits 0 = [] digits n = rem n 10 : digits (quot n 10) -- And divides function divides :: Int -> Int -> Bool divides divisor n = 0 == rem n divisor ===== (define check-isbn ;book number (make-verifier * 11)) (define check-upc ;universal product code (make-verifier (lambda (i d) (if (odd? i) d (* 3 d))) 10)) (define check-cc ;credit card (make-verifier (lambda (i d) (if (odd? i) d (if (< d 5) (* 2 d) (+ (* 2 d) 1)))) 10)) (define check-usps ;postal money order (make-verifier (lambda (i d) (if (= i 1) (- d) d)) 9))

4 3

GHC RTS bug: segmentation fault
by Manlio Perillo 12 Apr '09

12 Apr '09

Hi. In a program I have experienced a segmentation fault; not only that but also: * tpp.c:63: __pthread_tpp_change_priority: Assertion `new_prio == -1 || (new_prio >= __sched_fifo_min_prio && new_prio <= __sched_fifo_max_prio)' failed. * internal error: removeThreadFromQueue: not found (GHC version 6.8.2 for i386_unknown_linux) Please report this as a GHC bug: http://www.haskell.org/ghc/reportabug I have managed to write a program that reproduces the problem: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=3714 Compile with: $ghc --make -threaded -O2 main.hs Execute with: $./main +RTS -A128M -s -c -N4 -RTS 5000000 500 This should produce a segmentation fault (or one of the previous errors). I strongly suspect that the cause is an uncaught stack overflow. Executing the code with only 1 threads, there are no more problems. Increasing the thread stack size (-k1M), there are no more problems. If the problem is really an uncaught stack overflow, I'm rather sure that a more simple test can be written, to reproduce the problem. I'm on Linux Debian Etch i386; GHC 6.8.2. Some notes about the program: - when no segmentation fault occurs, the program requires about 1 GB of memory - there is no real parallelization, only 1 CPU is used - the mapReduce implementation is taken from Real World Haskell - the code is adapted from the code I'm using in a project Thanks Manlio Perillo

2 1

Re: [Haskell-cafe] Functions that return functions
by michael rice 12 Apr '09

12 Apr '09

Cool. I expected as much. My ISP seems to be swamped (Easter?) so maybe more later after I look at your remarks. Thanks. Michael --- On Sun, 4/12/09, Daniel Fischer <daniel.is.fischer(a)web.de> wrote: From: Daniel Fischer <daniel.is.fischer(a)web.de> Subject: Re: [Haskell-cafe] Functions that return functions To: haskell-cafe(a)haskell.org Cc: "michael rice" <nowgate(a)yahoo.com> Date: Sunday, April 12, 2009, 12:15 PM Am Sonntag 12 April 2009 17:38:53 schrieb michael rice: > The following are exercises 5.10, and 5.11 from the Scheme text "Concrete > Abstractions" by Max Hailperin, et al. The text at that point is about > writing verifiers to check ID numbers such as ISBNs, credit card numbers, > UPCs, etc. > > ====== > > Exercise 5.10 > Write a predicate that takes a number and determines whether the sum of its > digits is divisible by 17. > > Exercise 5.11 > Write a procedure make-verifier, which takes f and m as its two arguments > and returns a procedure capable of checking a number. The argument f is > itself a procedure of course. Here is a particularly simple example of a > verifier being made and used. > > (define check-isbn (make-verifier * 11)) > > (check-isbn 0262010771) > #t > > The value #t is the "true" value; it indicates that the number is a valid > ISBN. > > As we just saw, for ISBN numbers the divisor is 11 and the function is > simply f(i,d(i)) = i * d(i). Other kinds of numbers use slightly more > complicated functions, but you will still be able to use make-verifier to > make a verifier much more easily than if you had to start from scratch. > > ======= > > Here's the Scheme check-verifier function I wrote, followed by my humble > attempt at a Haskell function that does the same thing. Below that are some > verifier functions created with the Scheme make-verifier. Admittedly, > functions that return functions are Lispy, but perhaps there a Haskelly way > to accomplish the same thing? Functions returning functions are quite natural in Haskell. Since usually functions are written in curried form, a function returng a function corresponds to a function of multiple arguments applied to only some of them. > > Michael > > =============== > > > (define (make-verifier f m) ;f is f(i,d) & m is divisor > (lambda (n) > (let* ((d (digits n)) > (i (index (length d)))) ;(index 3) => (1 2 3) > (divides? m (reduce + 0 (map f i d)))))) #f > > makeVerifier :: (Int -> Int -> Int) -> Int -> (Int -> Bool) > > makeVerifier f m = \n -> let d = digits n > > i = [1..(length d)] > > in \n -> divides m (foldl (+) 0 (map2 f i d)) > > makeVerifier f m n = divides m . foldl (+) 0 $ zipWith f [1 .. ] (digits n) just call makeVerifier f m to get your verification function :) If you don't want to name the last argument: makeVerifier f m = divides m . foldl (+) 0 . zipWith f [1 .. ] . digits more point-freeing would be obfuscation. Instead of foldl (+) 0, you could also just write sum. > > -- Note: Reduce is just foldl f 0 lst, but map2 is > map2 :: (Int -> Int -> Int) -> [Int] -> [Int] -> [Int] > map2 f m n = [ f i d | (i,d) <- zip m n] map2 is zipWith, already in the Prelude. > > -- And here's my digits function > digits :: Int -> [Int] > digits 0 = [] > digits n = rem n 10 : digits (quot n 10) Unless you are desperate for speed and sure you deal only with positive numbers (or know that you really want quot and rem), better use div and mod. Those give the commonly expected (unless your expectation has been ruined by the behaviour of % in C, Java...) results. > > -- And divides function > divides :: Int -> Int -> Bool > divides divisor n = 0 == rem n divisor > > ===== > > (define check-isbn ;book number > (make-verifier > * > 11)) > > (define check-upc ;universal product code > (make-verifier > (lambda (i d) (if (odd? i) d (* 3 d))) > 10)) > > (define check-cc ;credit card > (make-verifier > (lambda (i d) (if (odd? i) d (if (< d 5) (* 2 d) (+ (* 2 d) 1)))) > 10)) > > (define check-usps ;postal money order > (make-verifier > (lambda (i d) (if (= i 1) (- d) d)) > 9))

1 0

Broken beyond repair: Control.Concurrent.SampleVar
by ChrisK 12 Apr '09

12 Apr '09

Hello all, The SampleVar module in base is not exception safe. I believe that there is no way to fix this module to be exception safe while retaining the current behavior. The problem with the current behavior is that the writeSampleVar pretends to know how many blocked reader threads are waiting on a value. In reality these blocked threads may have been killed. When writeSampleVar sees blocked threads it does a blocking putMVar and then decrements the blocked reader thread count. If any two of the blocked reader threads ever die then eventually you get a blocked writer. I can find no efficient way to retain the current behavior in the presence of exceptions. The logic of the current behavior is that the blocked readers mean that the previously written value should not be discarded, the previous value belongs to the next blocked reader. I propose that SampleVar be either removed, or replaced with a slightly different exception safe version. I propose not considering the previously written value to belong to a blocked reader, and to replace it with the new value. I will open a ticket about this when I get more time. -- Chris

1 0

Bug in Data.Stream?
by Peter Verswyvelen 12 Apr '09

12 Apr '09

Since I realized my code was always using infinite lists, I replaced it by Data.Stream. However, my code stopped working. The problem is with these functions: scan :: (a -> b -> a) -> a -> Stream b -> Stream ascan f z (Cons x xs) = z <:> scan f (f z x) xs-- | @scan'@ is a strict scan.scan' :: (a -> b -> a) -> a -> Stream b -> Stream ascan' f z (Cons x xs) = z <:> (scan' f $! (f z x)) xs They are too strict I think. My code works again when I add a lazy pattern match: scan f z ~(Cons x xs) = z <:> scan f (f z x) xs scan' f z ~(Cons x xs) = z <:> (scan' f $! (f z x)) xs This is justified since they then behave like scanl on lists. However it seems this package is used a lot, so maybe some code depends on this strictness. What to do? PS: Why does scanl' not exist in Data.List?

2 2

How to get glyph outline from ttf font.
by Dmitry V'yal 11 Apr '09

11 Apr '09

Greetings. I'm trying to render some glyphs from ttf font to svg image using gtk2hs cairo binding. Since I can find nothing appropriate in gtk2hs API, I decided to draw outlines with bezier curves myself. But how to get them out of font? As far as I know, freetype library is capable of extracting outlines, but is there any haskell binding for it which supports this functionality? Here [1] one such lib was mentioned, but it wasn't availible online that time. Have situation changed today? Thanks in advance [1] http://www.nabble.com/Re%3A-Rendering-TTF-fonts-in-Haskell-and-OpenGL-p1563…

4 3

what does the hidden package error mean?
by Anatoly Yakovenko 11 Apr '09

11 Apr '09

I am trying to build ParseP on the latest ghc, and i am getting this error: Text/ParserCombinators/ParseP/Interface.hs:26:17: Could not find module `Data.ByteString.Char8': it is a member of package bytestring-0.9.1.4, which is hidden what does "hidden" mean? why does this work in ghci > import Data.ByteString > import Data.ByteString.Char8 > without any problems

5 5