- Haskell-Cafe - Haskell.org

Sequence differences
by michael rice 13 Apr '09

13 Apr '09

I have a Scheme function that calculates sequence differences, i.e., it returns a sequence that is the difference between the 2nd and the 1st element, the 3rd and the 2nd, the 4th and the 3rd, etc. (define s (lambda (f l) (cond ((null? (cdr l)) '()) (else (cons (f (cadr l) (car l)) (s f (cdr l))))))) where (s - '(0,1,3,6,10,15,21,28)) => (1,2,3,4,5,6,7) I'm thinking the same function in Haskell would be something like s :: s f [] = [] s f [x] = [x] s f l = [ a f b | (a,b) <- zip (init l) (tail l)] but can't figure out what the function typing would be. Michael

5 4

binary package: memory problem decoding an IntMap
by Manlio Perillo 13 Apr '09

13 Apr '09

Hi. I'm having memory problems decoding a big IntMap. The data structure is: IntMap (UArr (Word16 :*: Word8)) There are 480189 keys, and a total of 100480507 elements (Netflix Prize). The size of the encoded (and compressed) data is 184 MB. When I load data from the Netflix Prize data set, total memory usage is 1030 Mb. However when I try to decode the data, memory usage grows too much (even using the -F1.1 option in the RTS). The problem seems to be with `fromAscList` function, defined as: fromList :: [(Key,a)] -> IntMap a fromList xs = foldlStrict ins empty xs where ins t (k,x) = insert k x t (by the way, why IntMap module does not use Data.List.foldl'?). The `ins` function is not strict. This seems an hard problem to solve. First of all, IntMap should provide strict variants of the implemented functions. And the binary package should choose whether use the strict or lazy version. For me, the simplest solution is to serialize the association list obtained from `toAscList` function, instead of directly serialize the IntMap. The question is: can I "reuse" the data already serialized? Is the binary format of `IntMap a` and `[(Int, a)]` compatible? Thanks Manlio Perillo

2 4

Control.Concurrent export/import weirdness
by Jason Dusek 13 Apr '09

13 Apr '09

Why is this function exported then imported? foreign export ccall forkOS_entry :: StablePtr (IO ()) -> IO () foreign import ccall "forkOS_entry" forkOS_entry_reimported :: StablePtr (IO ()) -> IO () forkOS_entry :: StablePtr (IO ()) -> IO () forkOS_entry stableAction = do action <- deRefStablePtr stableAction action -- Jason Dusek

2 1

understanding typeable
by Anatoly Yakovenko 13 Apr '09

13 Apr '09

i am trying to figure out how typeable works, so i have this data type data Foo = FooC Int deriving (Data, Typeable, Show) So how come this works: > funResultTy (typeOf ((+) 1)) (typeOf 1) Just Integer but this doesnt: > funResultTy (typeOf FooC) (typeOf 1) Nothing FooC is of type t -> u and 1 is of type t so the result should be u? I don't think t and u need to be the same since > funResultTy (typeOf (\a -> a:[1])) (typeOf 1) Just [Integer] works fine. So given a constructor, how come i cant seem to construct a type out of it?

2 3

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

13 Apr '09

I'm not sure what you're trying to tell me, so let's try a specific case. Here's the makeVerifier function that expects its function f to have a single arg, a pair (i,d): makeVerifier :: ((Int,Int) -> Int) -> Int -> (Int -> Bool) makeVerifier f m = divides m . foldl (+) 0 . map f . zip [1 .. ] . digits And usage: let checkCc = makeVerifier (\ (i d) -> if odd i then d else if d < 5 then 2*d else 2*d + 1) 10 And here's the old makeVerifier function that expects its function f to have two integer arguments, i & d: makeVerifier :: (Int -> Int -> Int) -> Int -> (Int -> Bool) makeVerifier f m = divides m . foldl (+) 0 . zipWith f [1 .. ] . digits And usage: let checkCc = makeVerifier (\ .... <== Complete this ) 10 Michael --- On Sun, 4/12/09, Ross Mellgren <rmm-haskell(a)z.odi.ac> wrote: From: Ross Mellgren <rmm-haskell(a)z.odi.ac> Subject: Re: [Haskell-cafe] Functions that return functions To: "michael rice" <nowgate(a)yahoo.com> Cc: "Daniel Fischer" <daniel.is.fischer(a)web.de>, haskell-cafe(a)haskell.org Date: Sunday, April 12, 2009, 9:23 PM Under the covers of syntax they only have one parameter, but you can write curried lambdas or functions easily: \ a b -> a + b which is equivalent to \ a -> \ b -> a + b and also equivalent to the "normal" function syntax f a b = a + b or f a = \ b -> a + b -Ross On Apr 12, 2009, at 9:09 PM, michael rice wrote: My question was meant in the context of the makeVerifier function, which is passed a lambda expression. It's my understanding that Haskell lambda expressions can have only a single parameter, which is why I changed the function parameter to a pair, (i,d). How would it be done otherwise? 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: "michael rice" <nowgate(a)yahoo.com> Cc: haskell-cafe(a)haskell.org Date: Sunday, April 12, 2009, 7:20 PM Am Montag 13 April 2009 01:09:22 schrieb michael rice: > Example please. > > Michael > Curried: f :: a -> b -> c amenable to partial application. Uncurried: g :: (a,b) -> c not easy to apply partially. The Prelude contains curry :: ((a,b) -> c) -> (a -> b -> c) uncurry :: (a -> b -> c) -> ((a,b) -> c) to convert if needed. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1

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

13 Apr '09

My question was meant in the context of the makeVerifier function, which is passed a lambda expression. It's my understanding that Haskell lambda expressions can have only a single parameter, which is why I changed the function parameter to a pair, (i,d). How would it be done otherwise? 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: "michael rice" <nowgate(a)yahoo.com> Cc: haskell-cafe(a)haskell.org Date: Sunday, April 12, 2009, 7:20 PM Am Montag 13 April 2009 01:09:22 schrieb michael rice: > Example please. > > Michael > Curried: f :: a -> b -> c amenable to partial application. Uncurried: g :: (a,b) -> c not easy to apply partially. The Prelude contains curry :: ((a,b) -> c) -> (a -> b -> c) uncurry :: (a -> b -> c) -> ((a,b) -> c) to convert if needed.

2 1

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

13 Apr '09

No sweat. My comment was meant humorously. I just forgot the emoticon. Any way you look at it, Haskell is very impressive, and I've just scratched the surface. 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, 7:27 PM michael rice wrote: > You're getting ahead of me again. I'm sorry. I didn't expect you to understand the whole thing. Rather, I'm just showing what is possible. Notice that there is no lambda abstraction in the function implementation. The entire thing is constructed with combinators, functions that take other functions as arguments. I was trying to emphasize that it is very Haskelly to accept and return functions as happily as normal values. - Jake

1 0

History data structure suggestion
by Victor Nazarov 13 Apr '09

13 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