• Choose a category
• All
• Classic-Fiction

By Root 506 0

make a normal list into a difference list, we just do what we did before and make it a function that prepends it to another list. Because a difference list is a function that prepends something to another list, if we just want that something, we apply the function to an empty list!

Here’s the Monoid instance:

instance Monoid (DiffList a) where

mempty = DiffList (\xs -> [] ++ xs)

(DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))

Notice how for lists, mempty is just the id function, and mappend is actually just function composition. Let’s see if this works:

ghci> fromDiffList (toDiffList [1,2,3,4] `mappend` toDiffList [1,2,3])

[1,2,3,4,1,2,3]

Tip-top! Now we can increase the efficiency of our gcdReverse function by making it use difference lists instead of normal lists:

import Control.Monad.Writer

gcd' :: Int -> Int -> Writer (DiffList String) Int gcd' a b

| b == 0 = do

tell (toDiffList ["Finished with " ++ show a])

return a

| otherwise = do

result <- gcd' b (a `mod` b)

tell (toDiffList [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)])

return result

We just needed to change the type of the monoid from [String] to DiffList String and then when using tell, convert our normal lists into difference lists with toDiffList. Let’s see if the log gets assembled properly:

ghci> mapM_ putStrLn . fromDiffList . snd . runWriter $ gcdReverse 110 34

Finished with 2

8 mod 2 = 0

34 mod 8 = 2

110 mod 34 = 8

We do gcdReverse 110 34, then use runWriter to unwrap it from the newtype, then apply snd to that to just get the log, then apply fromDiffList to convert it to a normal list, and, finally, print its entries to the screen.

Comparing Performance

To get a feel for just how much difference lists may improve your performance, consider the following function. It just counts down from some number to zero but produces its log in reverse, like gcdReverse, so that the numbers in the log will actually be counted up.

finalCountDown :: Int -> Writer (DiffList String) ()

finalCountDown 0 = do

tell (toDiffList ["0"])

finalCountDown x = do

finalCountDown (x-1)

tell (toDiffList [show x])

If we give it 0, it just logs that value. For any other number, it first counts down its predecessor to 0, and then appends that number to the log. So, if we apply finalCountDown to 100, the string "100" will come last in the log.

If you load this function in GHCi and apply it to a big number, like 500000, you’ll see that it quickly starts counting from 0 onward:

ghci> mapM_ putStrLn . fromDiffList . snd . runWriter $ finalCountDown 500000

0

1

2

...

However, if you change it to use normal lists instead of difference lists, like so:

finalCountDown :: Int -> Writer [String] ()

finalCountDown 0 = do

tell ["0"]

finalCountDown x = do

finalCountDown (x-1)

tell [show x]

and then tell GHCi to start counting:

ghci> mapM_ putStrLn . snd . runWriter $ finalCountDown 500000

you’ll see that the counting is really slow.

Of course, this is not the proper and scientific way to test the speed of your programs. However, we were able to see that, in this case, using difference lists starts producing results immediately, whereas normal lists take forever.

Oh, by the way, the song “Final Countdown” by Europe is now stuck in your head. Enjoy!

Reader? Ugh, Not This Joke Again

In Chapter 11, you saw that the function type (->) r is an instance of Functor. Mapping a function f over a function g will make a function that takes the same thing as g, applies g to it, and then applies f to that result. So basically, we’re making a new function that’s like g, but before returning its result, f is applied to that result as well. Here’s an example:

ghci> let f = (*5)

ghci> let g = (+3)

ghci> (fmap f g) 8

55

You’ve also seen that functions are applicative functors. They allow us to operate on the eventual results of functions as if we already had their results. Here’s an example:

ghci> let f = (+) <$> (*2) <*> (+10)

ghci> f 3

19

The expression (+) <$> (*2) <*> (+10) makes a function that takes a number, gives