Send Beginners mailing list submissions to beginners@haskell.org To subscribe or unsubscribe via the World Wide Web, visit http://www.haskell.org/mailman/listinfo/beginners or, via email, send a message with subject or body 'help' to beginners-requ...@haskell.org
You can reach the person managing the list at beginners-ow...@haskell.org When replying, please edit your Subject line so it is more specific than "Re: Contents of Beginners digest..." Today's Topics: 1. Re: about parser question < Programming in haskell _ chapter 8 > (Haisheng Wu) 2. Re: Impossible lib definition? (Christian Maeder) 3. Error in converting the function from let in clause to where (mukesh tiwari) ---------------------------------------------------------------------- Message: 1 Date: Mon, 18 Jul 2011 19:17:36 +0800 From: Haisheng Wu <fre...@gmail.com> Subject: Re: [Haskell-beginners] about parser question < Programming in haskell _ chapter 8 > To: anyzhen <jiangzhe...@qq.com> Cc: Beginners <Beginners@haskell.org> Message-ID: <cafj8lzfrkgnz7gsbj6fbkt_n+q5636ulyq7qe8t98umpnv_...@mail.gmail.com> Content-Type: text/plain; charset="iso-8859-1" I think you can check full source code at its web site to see what you missed. My thought: did you make Parser as a instance of Monad? -Haisheng On Mon, Jul 18, 2011 at 5:20 PM, anyzhen <jiangzhe...@qq.com> wrote: > 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:jiangzhe...@qq.com>* > > _______________________________________________ > Beginners mailing list > Beginners@haskell.org > http://www.haskell.org/mailman/listinfo/beginners > > -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://www.haskell.org/pipermail/beginners/attachments/20110718/ea7911ed/attachment-0001.htm> ------------------------------ Message: 2 Date: Mon, 18 Jul 2011 15:55:55 +0200 From: Christian Maeder <christian.mae...@dfki.de> Subject: Re: [Haskell-beginners] Impossible lib definition? To: Obscaenvs 74 <obscae...@gmail.com> Cc: beginners@haskell.org Message-ID: <4e243b6b.8010...@dfki.de> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Am 18.07.2011 10:27, schrieb Obscaenvs 74: > From the source of the package Text.ParserCombinators.ReadP, available > at > http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/Text-ParserCombinators-ReadP.html#many > : > > 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. "p" is a common (non-changing) argument for parsing exactly one occurrence. The termination is controlled by the choice operator +++ or the length of the input string, provided the argument "p" does consume at least one character from the input. HTH Christian > > /Fredrik > ------------------------------ Message: 3 Date: Mon, 18 Jul 2011 20:51:07 +0530 From: mukesh tiwari <mukeshtiwari.ii...@gmail.com> Subject: [Haskell-beginners] Error in converting the function from let in clause to where To: beginners@haskell.org Message-ID: <cafhzve-asd+f+w1gh889ue9q_a4rcs7v9tmv4yycpcfpepv...@mail.gmail.com> Content-Type: text/plain; charset="iso-8859-1" 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 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://www.haskell.org/pipermail/beginners/attachments/20110718/df660087/attachment.htm> ------------------------------ _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners End of Beginners Digest, Vol 37, Issue 33 *****************************************