Advertisement
Guest User

Untitled

a guest
Jan 31st, 2015
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.05 KB | None | 0 0
  1. module HsList ( List(..)
  2. , fromList
  3. , (+++)
  4. , singleton
  5. , map
  6. , length
  7. , intersperse
  8. , intercalate
  9. , concat
  10. , and
  11. , or
  12. , any
  13. , all
  14. , iterate
  15. , head
  16. , init
  17. , tail
  18. , last
  19. , take
  20. , drop
  21. , splitAt
  22. , takeWhile
  23. , span
  24. ) where
  25.  
  26. import Prelude hiding ( map
  27. , length
  28. , intersperse
  29. , intercalate
  30. , concat
  31. , iterate
  32. , splitAt
  33. , takeWhile
  34. , span
  35. , head
  36. , init
  37. , tail
  38. , last
  39. , take
  40. , drop
  41. , and
  42. , or
  43. , any
  44. , all)
  45.  
  46. data List a = a :+ (List a)
  47. | Nil
  48. infixr 4 :+
  49.  
  50. instance (Show a) => Show (List a) where
  51. show Nil = "[]"
  52. show xs = let str = mkString $ intersperse ", " $ map show xs
  53. in "[" ++ str ++ "]"
  54.  
  55. xs, ys :: List Int
  56. xs = 1 :+ 2 :+ 3 :+ Nil
  57. ys = 15 :+ 42 :+ 52 :+ 22 :+ Nil
  58.  
  59. xss :: List (List Int)
  60. xss = xs :+ ys :+ Nil
  61.  
  62. fromList :: [a] -> List a
  63. fromList = foldr (:+) Nil
  64.  
  65. (+++) :: List a -> List a -> List a
  66. Nil +++ ys = ys
  67. (x :+ xs) +++ ys = x :+ (xs +++ ys)
  68.  
  69. singleton :: a -> List a
  70. singleton x = x :+ Nil
  71.  
  72. length :: List a -> Int
  73. length Nil = 0
  74. length (_ :+ xs) = 1 + length xs
  75.  
  76. mkString :: List String -> String
  77. mkString Nil = ""
  78. mkString (cs :+ css) = cs ++ mkString css
  79.  
  80. head :: List a -> Maybe a
  81. head Nil = Nothing
  82. head (x :+ _) = Just x
  83.  
  84. init :: List a -> List a
  85. init Nil = error "init: empty list"
  86. init (x :+ y :+ Nil) = singleton x
  87. init (x :+ xs) = x :+ (init xs)
  88.  
  89. tail :: List a -> List a
  90. tail Nil = Nil
  91. tail (x :+ xs) = xs
  92.  
  93. last :: List a -> Maybe a
  94. last Nil = Nothing
  95. last (x :+ Nil) = Just x
  96. last (x :+ xs) = last xs
  97.  
  98. map :: (a -> b) -> List a -> List b
  99. map _ Nil = Nil
  100. map f (x :+ xs) = f x :+ map f xs
  101.  
  102. intersperse :: a -> List a -> List a
  103. intersperse _ Nil = Nil
  104. intersperse _ l@(x :+ Nil) = l
  105. intersperse y (x :+ xs) = x :+ y :+ (intersperse y xs)
  106.  
  107. concat :: List (List a) -> List a
  108. concat Nil = Nil
  109. concat (xs :+ xss) = xs +++ (concat xss)
  110.  
  111. intercalate :: List a -> List (List a) -> List a
  112. intercalate ys xss = concat (intersperse ys xss)
  113.  
  114. and :: List Bool -> Bool
  115. and Nil = True
  116. and (b :+ bs) = b && (and bs)
  117.  
  118. or :: List Bool -> Bool
  119. or Nil = False
  120. or (b :+ bs) = b || (or bs)
  121.  
  122. any :: (a -> Bool) -> List a -> Bool
  123. any _ Nil = False
  124. any p (x :+ xs) = p x || (any p xs)
  125.  
  126. all :: (a -> Bool) -> List a -> Bool
  127. all _ Nil = True
  128. all p (x :+ xs) = p x && (all p xs)
  129.  
  130. iterate :: (a -> a) -> a -> List a
  131. iterate step v = v :+ iterate step (step v)
  132.  
  133. take :: Int -> List a -> List a
  134. take _ Nil = Nil
  135. take n (x :+ xs) | n > 0 = x :+ take (n - 1) xs
  136. | otherwise = Nil
  137.  
  138. drop :: Int -> List a -> List a
  139. drop _ Nil = Nil
  140. drop n l@(x :+ xs) | n > 0 = drop (n - 1) xs
  141. | otherwise = l
  142.  
  143. splitAt :: Int -> List a -> (List a, List a)
  144. splitAt _ Nil = (Nil, Nil)
  145. splitAt 0 xs = (Nil, xs)
  146. splitAt n (x :+ xs) = let (fst, snd) = splitAt (n - 1) xs
  147. in if n > 0
  148. then (x :+ fst, snd)
  149. else (fst, x :+ snd)
  150.  
  151. takeWhile :: (a -> Bool) -> List a -> List a
  152. takeWhile _ Nil = Nil
  153. takeWhile p (x :+ xs) = if p x
  154. then x :+ takeWhile p xs
  155. else Nil
  156.  
  157.  
  158. span :: (a -> Bool) -> List a -> (List a, List a)
  159. span _ Nil = (Nil, Nil)
  160. span p rest@(x :+ xs) = if p x
  161. then let (fst, snd) = span p xs
  162. in (x :+ fst, snd)
  163. else (Nil, rest)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement