- Beginners - Haskell.org

Error in converting the function from let in clause to where
by mukesh tiwari 19 Jul '11

19 Jul '11

Hello all This is my first post on Haskell-beginner so i am not completely aware of protocols here . Pardon me for my ignorance . I am trying to implement elliptic curve prime factorisation and initially wrote function "addPoints" using let in clause. It works fine. When i converted the "addPoint" using where clause then its not working and not adding the points correctly . I run both functions from ghci and for same point " addPoints ( Conelliptic 1222 34 5678 ) ( Conpoint 123 42567 ) ( Conpoint 1234 4322222222222222) " addPoints function using where clause return Right 2 while let in clause return Left (Conpoint 4840 4122) . Could some one please help me to find out the bug . In case of indentation problem , source code on http://hpaste.org/49174 . Regards Mukesh Tiwari --y^2= x^3+ax+b mod n import Random import Control.Monad import Data.List import Data.Bits data Elliptic = Conelliptic Integer Integer Integer deriving ( Eq , Show ) data Point = Conpoint Integer Integer | Identity deriving ( Eq , Show ) powM :: Integer -> Integer -> Integer -> Integer powM a d n | d == 0 = 1 | d == 1 = mod a n | otherwise = mod q n where p = powM ( mod ( a^2 ) n ) ( shiftR d 1 ) n q = if (.&.) d 1 == 1 then mod ( a * p ) n else p calSd :: Integer -> IO ( Integer , Integer ) calSd n = return ( s , d ) where s = until ( \x -> testBit ( n - 1) ( fromIntegral x ) ) ( +1 ) 0 d = div ( n - 1 ) ( shiftL 1 ( fromIntegral s ) ) isProbable::Integer->IO Bool isProbable n | n <= 1 = return False | n == 2 = return True | even n = return False | otherwise = calSd n >>= (\( s , d ) -> rabinMiller 0 n s d ) rabinMiller::Integer->Integer->Integer->Integer->IO Bool rabinMiller cnt n s d | cnt>=5= return True | otherwise = randomRIO ( 2 , n - 2 ) >>= (\a -> case powM a d n == 1 of True -> rabinMiller ( cnt + 1 ) n s d _ -> if any ( == pred n ) . take ( fromIntegral s ) . iterate (\e -> mod ( e^2 ) n ) $ powM a d n then rabinMiller ( cnt + 1) n s d else return False ) {-- --add points of elliptic curve addPoints :: Elliptic -> Point -> Point -> Either Point Integer addPoints _ Identity p_2 = Left p_2 addPoints _ p_1 Identity = Left p_1 addPoints ( Conelliptic a b n ) ( Conpoint x_p y_p ) ( Conpoint x_q y_q ) | x_p /= x_q = case ( ( Conpoint x_r y_r ) , d ) of ( _ , 1 ) -> Left ( Conpoint x_r y_r ) ( _ , d' ) -> Right d' where [ u , v , d ] = extended_gcd ( x_p - x_q ) n s = mod ( ( y_p - y_q ) * u ) n x_r = mod ( s*s - x_p - x_q ) n y_r = mod ( -y_p - s * ( x_r - x_p ) ) n | otherwise = if mod ( y_p + y_q ) n == 0 then Left Identity else case ( ( Conpoint x_r y_r ) , d ) of ( _ , 1 ) -> Left ( Conpoint x_r y_r ) ( _ , d' ) -> Right d' where [ u , v , d ] = extended_gcd ( 2 * y_p ) n s = mod ( ( 3 * x_p * x_p + a ) * u ) n x_r = mod ( s * s - 2 * x_p ) n y_r = mod ( -y_p - s * ( x_r - x_p ) ) n --} --add points of elliptic curve addPoints::Elliptic->Point->Point-> Either Point Integer addPoints _ Identity p_2 = Left p_2 addPoints _ p_1 Identity = Left p_1 addPoints ( Conelliptic a b n ) ( Conpoint x_p y_p ) ( Conpoint x_q y_q ) | x_p /= x_q = let [ u , v , d ] = extended_gcd (x_p-x_q) n s = mod ( ( y_p - y_q ) * u ) n x_r = mod ( s * s - x_p - x_q ) n y_r= mod ( -y_p - s * ( x_r - x_p ) ) n in case ( ( Conpoint x_r y_r ) , d ) of ( _ , 1 ) -> Left ( Conpoint x_r y_r ) ( _ , d' ) -> Right d' | otherwise = if mod ( y_p + y_q ) n == 0 then Left Identity else let [ u , v , d ] = extended_gcd ( 2*y_p ) n s = mod ( ( 3 * x_p * x_p + a ) * u ) n x_r = mod ( s * s - 2 * x_p ) n y_r = mod ( -y_p - s * ( x_r - x_p ) ) n in case ( ( Conpoint x_r y_r ) , d ) of ( _ , 1 )-> Left (Conpoint x_r y_r) ( _ , d' ) -> Right d' extended_gcd::Integer->Integer->[Integer] extended_gcd u v= helpGcd u v 0 [ [ 1 , 0 ] , [ 0 , 1 ] ] where helpGcd u v n m @ ( [ [ a , b ] , [ c , d ] ] ) | v == 0 = if u<0 then [ - ( ( -1 ) ^ n ) * ( m !! 1 !! 1 ) , - ( ( -1 ) ^ ( n + 1 ) ) * ( m !! 0 !! 1 ) , -u ] else [ ( ( -1 ) ^ n ) * ( m !! 1 !! 1 ) , ( ( -1 ) ^ ( n + 1 ) ) * ( m !! 0 !! 1 ) , u ] | otherwise = helpGcd u' v' ( n + 1 ) m' where ( q , v' ) = quotRem u v t = [ [q , 1 ] , [ 1 , 0 ] ] m' = [ [ q * a + b , a ] , [ q * c + d , c ] ] --mult m t u' = v multiEC :: Elliptic -> Point -> Integer -> IO ( Either Point Integer ) multiEC _ _ 0 = return $ Left Identity multiEC ecurve point k | k>0 = return $ helpEC Identity point k where helpEC p _ 0 = Left p helpEC p q n = case (p',q') of ( Left p'' , Left q'' ) -> helpEC p'' q'' (div n 2) ( Right p'' , _ ) -> Right p'' ( _ , Right q'' ) -> Right q'' where p' =if odd n then addPoints ecurve p q else Left p q' = addPoints ecurve q q dscrmntEC a b = 4 * a * a * a + 27 * b * b randomCurve :: Integer -> IO [Integer] randomCurve n = randomRIO ( 1 , n ) >>= ( \a -> randomRIO ( 1 , n ) >>= ( \u -> randomRIO (1 , n) >>= (\v -> return [a , mod ( v*v - u*u*u - a*u ) n , n , u , v ] ) ) ) factor :: Integer -> Integer -> IO [Integer] factor 1 _ = return [] factor n m = isProbable n >>= (\x -> if x then return [n] else randomCurve n >>= (\[ a , b , n , u , v ] -> multiEC ( Conelliptic a b n ) ( Conpoint u v ) m >>= ( \p -> case p of Left p' -> factor n m Right p'-> factor ( div n p' ) m >>= ( \x -> factor p' m >>= (\y -> return $ x ++ y ) ) ) ) ) solve :: Integer -> IO [ Integer ] solve n = factor n ( foldl lcm 1 [1..10000] ) main = liftM read getLine >>=( \n -> solve n ) >>= print

2 1

FW: question
by Roelof Wobben 19 Jul '11

19 Jul '11

Oke, I tried with Ghci 7.03 on the prompt but then I see this: [x^2 | x <-- [1..100] not in scope x not in scope <-- When I put the text in a file I see these errors. parse error : naked expression at top level. Roelof > > > > ---------------------------------------- > > Date: Wed, 13 Jul 2011 23:04:58 +0200 > > From: andres.loeh(a)googlemail.com > > To: beginners(a)haskell.org > > Subject: Re: [Haskell-beginners] question > > > > I've just tried to evaluate 2 ^ 5 in codepad and it worked for me, so > > (^) seems to be supported. > > > > Cheers, > > Andres > > > > _______________________________________________ > > Beginners mailing list > > Beginners(a)haskell.org > > http://www.haskell.org/mailman/listinfo/beginners

8 12

about parser question < Programming in haskell _ chapter 8 >
by anyzhen 19 Jul '11

19 Jul '11

well,i am reading the book :<Programming in haskell > chapter 8 functional parsers this chapter try teaching an parser technology,but i have some problem about do keyword --some brief info of types : type Parser a = String -> [(a,String)] item :: Parser Char --item "abc" = [('a',"bc")] return' :: a -> Parser a --return' 'a' "foo" = [('a',"foo")] --below code complier notice... sorry format p2 :: Parser (Char,Char) p2 = do x <- item item y <- item return' (x,y) "No instance for (Monad ((-)) String)) arising from a execute statement Possible fix : add an instance declaration for (Monad ((-)) String)) In a stmt of a 'do' expression : y <- item In the expression: do { x <- item; item; y <- item; return' (x,y)} In an equation for 'p2': p2 = do { x <- item; item; y <- item; ....}" thanks for any help jiangzhen <mail:jiangzhen3s@qq.com>

3 2

Impossible lib definition?
by Obscaenvs 74 18 Jul '11

18 Jul '11

>From the source of the package Text.ParserCombinators.ReadP, available at http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/Text-P… : many :: ReadP a -> ReadP [a] -- ^ Parses zero or more occurrences of the given parser. many p = return [] +++ many1 p many1 :: ReadP a -> ReadP [a] -- ^ Parses one or more occurrences of the given parser. many1 p = liftM2 (:) p (many p) So `many` is defined in terms of `many1` and vice versa - completely understandable, but here the argument (`p`) does not change. This is above me right now. Anyone care to explain? I'd be grateful. Not that I have to understand it, but it keeps pestering me during my lonely hours. /Fredrik

2 1

cabal install reactive-banana-wx
by Tom Murphy 18 Jul '11

18 Jul '11

Install troubles! (Is the right place for this type of message?) Thanks! Tom $ cabal install reactive-banana-wx Resolving dependencies... cabal: cannot configure wxdirect-0.12.1.3. It requires containers >=0.2 && <0.4 For the dependency on containers >=0.2 && <0.4 there are these packages: containers-0.2.0.0, containers-0.2.0.1 and containers-0.3.0.0. However none of them are available. containers-0.2.0.0 was excluded because containers-0.4.0.0 was selected instead containers-0.2.0.0 was excluded because reactive-banana-0.4.1.0 requires containers ==0.4.* containers-0.2.0.1 was excluded because containers-0.4.0.0 was selected instead containers-0.2.0.1 was excluded because reactive-banana-0.4.1.0 requires containers ==0.4.* containers-0.3.0.0 was excluded because containers-0.4.0.0 was selected instead containers-0.3.0.0 was excluded because reactive-banana-0.4.1.0 requires containers ==0.4.*

4 3

Re: [Haskell-beginners] Looking for a datastructure
by David Place 17 Jul '11

17 Jul '11

On Jul 17, 2011, at 3:57 AM, Kees Bleijenberg wrote: > 2. A fast way to find the key with the lowest map-value (without traversing > the whole map). I see. If you were to implement it without worrying about the performance, you could just use a map and compute a fold over the map to find the min value. To have better performance, you want to incrementally recompute the fold at each update. This is the topic of an article that I wrote for the Monad.Reader called "How to refold a map." > http://www.haskell.org/wikiupload/6/6a/TMR-Issue11.pdf I show how to modify Data.Map for that purpose. Also, it turns out to be really nice to implement it in FingerTrees. If you would like I can post that too. ___________________ David Place Owner, Panpipes Ho! LLC http://panpipesho.com d(a)vidplace.com

1 0

Anyone have problems with cabal and SDL?
by Tom Murphy 17 Jul '11

17 Jul '11

When I use Cabal to get any program which depends on the SDL library, this is the error I get. " checking for sdl-config... no checking for sdl11-config... no configure: error: *** SDL not found! Get SDL from www.libsdl.org. If you already installed it, check it's in the path. If problem remains, please send a mail to the address that appears in ./configure --version indicating your platform, the version of configure script and the problem. cabal: Error: some packages failed to install: Raincat-1.1.1.2 depends on SDL-0.6.2 which failed to install. SDL-0.6.2 failed during the configure step. The exception was: exit: ExitFailure 1 SDL-image-0.6.1 depends on SDL-0.6.2 which failed to install. SDL-mixer-0.6.1 depends on SDL-0.6.2 which failed to install. " I have SDL 1.2.14 (correctly) installed on my system. I'd really appreciate any help with this. Tom

4 6

Pearls of Functional Algorithm Design, Chapter 2, The Surpasser Problem
by Costello, Roger L. 16 Jul '11

16 Jul '11

Hi Folks, I created Powerpoint slides to describe the algorithm for the "surpasser problem". Here is a motivation for the surpasser problem: Stock Market: Each day I record the closing value of the DOW. Occasionally, I pick a date and ask, "How many days after this date has the stock market closed at a higher value?" A more challenging question is, "Which day has the most number of following days where the stock market closed at a higher value?" People's Height: Line up a bunch of people. Pick one person and ask, "How many of the following people are taller than this person?" A more challenging question is, "Which person has the most number of following people that are taller?" Word Analysis: Take a letter in a word and ask, "How many of the following letters are bigger (occurs later in the alphabet) than this letter?" A more challenging question is, "Which letter has the most number of following letters that are bigger?" Thus we see a recurring problem: find the number of surpassers; or, find the maximum surpasser count. Recurring problems are good subjects for elegant algorithms. More ... http://www.xfront.com/Pearls-of-Functional-Algorithm-Design/Chapter2/surpas… /Roger

1 0

Monads in javascript
by Martin Drautzburg 16 Jul '11

16 Jul '11

Hello all, I found some implementations of Monads in javascript, but they all do not allow capturing the intermediate results. My question is: "what is the ultimate cause for this"? In haskell the second argument to (>>=) is a function a->Mb which can be written as a lambda expression, e.g. \x->[x]. In javascript such a function would be written as function(x) {return[x]}. Did I get this right: in haskell the chain of >>= is constructed from the end? So chaining a->Mb and b->Mc gives you a->Mc, which is again suitable as a second argument to (>>=), right? So why can't I do this is javascipt? Or can I? The reason I am asking this is because I am trying to beautify callbacks. An asynchronous ajax call needs a function argument, which will be executed once the call completes. But what if I want to take the results of the first call, do something with them and pass it to a second ajax call, where I would again have to pass another function argument. I would end up with a deeply nested structure of lambdas, something like f(a,b,...function(...){ ... g(... function(...) I had some hopes that chaining functions monad-style would ease my pain. I might be on the wrong track though, feel free to tell me so. -- Martin -- Martin

6 10

Looking for a datastructure
by Kees Bleijenberg 16 Jul '11

16 Jul '11

My program uses a very long list of (index,count) items. Index and count are Int's. The program updates the count values a lot. Therefor it uses the index as a key to update the belonging count value. After updating, the program needs the (index,count) pair with the least count value in the list. What is an approriate (fast) datastructure? My first idea was to use a heap. Problem with the heap is that I can't update the count value by its index fast. Any ideas? Kees

4 5