Recursion patterns, polymorphism, and the Prelude

Posted on 2015-08-17 01:13:17 +0900 in Functional Programming Haskell CIS194

Lecture Content

In fact, experienced Haskell programmers hardly ever write recursive functions!

This is quite unbelieable for me at first glance. Even though recursive function is not the best practice in languages which does not provide tail call optimization.

Recursive function provide more abstract way than iterative function, while there exists more abstract way than Recursive function, which leave the low-level details of actually doing recursion to these functions.

Infix Function

Backticks can turn any standard function with two argumetns in an infix operator which is called section syntax:

(op e)  =   \ x -> x op e
(e op)  =   \ x -> e op x

For example,

elem 2 [1, 2, 3] == (2 `elem`) [1, 2, 3] == ((`elem` [1, 2, 3]) 2)

Exercise 1 Hopscotch

zip or zipwith are convenient to do filter in list.

skips :: [a] -> [[a]]
skips xs =
        let ns = [1..length xs]
            extractEvery m = map snd . filter (\x -> (fst x `mod` m) == 0) . zip ns
            in map (`extractEvery` xs) ns

Exercise 2 Local maxima

localMaxima :: [Integer] -> [Integer]
localMaxima (a:b:c:xs)
    | b > a && b > c = b: p
    | otherwise = p
    where
        p = localMaxima(b:c:xs)
localMaxima _ = []

Exercise 3 Histogram

histogram:: [Integer] -> String
histogram xs =
        let count = map (\n -> length $ filter (== n) xs) [0..9]
            maxi = maximum count
            histo m (base, c) = show base ++ "=" ++
                replicate c '*' ++
                replicate (m - c) ' '
        in
           unlines . reverse . transpose . map (histo maxi) $ zip [0..9] count

Test code,

*Golf> putStr $ histogram [1,1,1,5]
 *        
 *        
 *   *    
==========
0123456789

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------

« Higher-order programming and type inference | Algebraic Data Types »