Advertisement
Guest User

Untitled

a guest
Dec 13th, 2015
148
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. {-# LANGUAGE FlexibleInstances #-}
  2. import Data.List hiding (permutations)
  3. import Control.Monad
  4. import Data.Ratio
  5.  
  6. data Exp a = Plus (Exp a) (Exp a) | Minus (Exp a) (Exp a) |
  7.              Mul (Exp a) (Exp a) | Div (Exp a) (Exp a) | Number a
  8.                                                                            
  9. instance (Show (Exp Rational)) where
  10.   show exp = case exp of
  11.     Number a -> show $ numerator a `div` denominator a
  12.     Plus a b -> "(" ++ show a ++ "+" ++ show b ++ ")"
  13.     Minus a b -> "(" ++ show a ++ "-" ++ show b ++ ")"
  14.     Mul a b -> "(" ++ show a ++ "*" ++ show b ++ ")"
  15.     Div a b -> "(" ++ show a ++ "/" ++ show b ++ ")"
  16.  
  17. eval exp = case exp of
  18.   Number a -> a
  19.   Plus a b -> eval a + eval b
  20.   Minus a b -> eval a - eval b
  21.   Mul a b -> eval a * eval b
  22.   Div a b -> eval a / eval b
  23.  
  24.  
  25. operations a b = if eval b == 0 then safeOps else Div a b:safeOps
  26.                                              where safeOps = [Plus a b, Minus a b, Mul a b]
  27. parseRational = Number . toRational . read
  28.  
  29. permutations :: String -> [Exp Rational]
  30. permutations [] = []
  31. permutations [x] = [parseRational [x]]
  32. permutations xs = do
  33.   (y:ys) <- map (map parseRational) $ combinations xs
  34.   foldM operations y ys
  35.     where
  36.       combinations :: [a] -> [[[a]]]
  37.       combinations [] = []
  38.       combinations [x] = [[[x]]]
  39.       combinations (x:xs) = map (\(y:ys) -> (x:y):ys) (combinations xs)  ++ map ([x]:) (combinations xs)
  40. main = do
  41.   number <- getLine
  42.   print $  filter ((== 100) . eval) $ permutations number
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement