# Exercise 6.2

`f :: a -> bf' :: a -> m aunit :: a -> m a`

`f' * g' = (bind f') . (bind g')`

``` bind f xs = concat (map f xs) ```

`bind unit xs = concat (map unit xs)`

`unit x = [x] `

``` ```

`bind unit xs = concat (map unit xs)= concat (map unit [x1, x2, ...])= concat [unit x1, unit x2, ...]= concat [[x1], [x2], ...]= [x1, x2, ...]= xs`

`f' = lift f`

``` ```

`lift f = unit . f`

`unit` (or `return`) can directly act on an ordinary value only, but not on a monadic value. To act on a monadic value, you need to `bind` it.

How come we do not need to lift `return`?

`f :: a -> b `

``` liftM :: Monad m => (a -> b) -> m a -> m b return :: a -> m a (liftM f) :: m a -> m b ```

`(>>=) :: Monad m => m a -> (a -> m b) -> m b`

`lifeM` cannot be applied to `return` at all.

`unit` (or `return`) is neither a pure function nor a monadic function. Instead, it is an half-monadic function, meaning that while its input is an ordinary value, its output is a monadic value.

`(bind return xs) -> ys`

`(bind return)` applies to `xs`.

`return` applies to `x`.

`liftM` is merely `fmap` implemented with `(>>=)` and `return`

— Me@2016-01-26 03:05:50 PM

# Exercise 6a (Corrected version)

Show that `f' * unit = unit * f' = bind f'`

——————————

`f :: a -> bf' :: a -> m aunit :: a -> m a`

`lift f = unit . ff' = lift f`

The `lift` function in this tutorial is not the same as the `liftM` in Haskell. So you should use `lift` (but not `liftM`) with `bind`.

— Me@2015-10-13 11:59:53 AM

`(f' * g') xs`
`= ((bind f') . (bind g')) xs`

`bind f' xs = concat (map f' xs)`
`unit x = [x]`

`bind unit xs = concat (map unit xs)= concat (map unit [x1, x2, ...])= concat [unit x1, unit x2, ...]= concat [[x1], [x2], ...]= [x1, x2, ...]= xs`

`(f' * unit) (x:xs)= bind f' (bind unit (x:xs))= bind f' (concat (map unit (x:xs)))= bind f' (concat (map unit [x1, x2, ...]))= bind f' (concat [[x1], [x2], ...])= bind f' [x1, x2, ...]= concat (map f' [x1, x2, ...])= concat [f' x1, f' x2, ...]= concat [(unit . f) x1, (unit . f) x2, ...]= concat [(unit (f x1)), (unit (f x2)), ...]= concat [[f x1], [f x2], ...]= [f x1, f x2, ...]`

`(unit * f') (x:xs)= ((bind unit) . (bind f')) (x:xs)= bind unit (bind f' (x:xs))= bind unit (concat (map f' (x:xs)))= bind unit (concat (map f' [x1, x2, ...]))= bind unit (concat [f' x1, f' x2, ...])= bind unit (concat [(unit . f)  x1, (unit . f) x2, ...])= bind unit (concat [(unit (f x1)), (unit (f x2)), ...])= bind unit (concat [[f x1], [f x2], ...])= bind unit [f x1, f x2, ...]= concat (map unit [f x1, f x2, ...])= concat [[f x1], [f x2], ...]= [f x1, f x2, ...]`

— Me@2015-10-15 07:19:18 AM

If we use the identity `bind unit xs = xs`, the proof will be much shorter.

`(f' * unit) (x:xs)= ((bind f') . (bind unit)) (x:xs)= bind f' (bind unit (x:xs))= bind f' (x:xs)`

`(unit * f') (x:xs)= ((bind unit) . (bind f')) (x:xs)= bind unit (bind f' (x:xs))= bind f' (x:xs)`

— Me@2015-10-15 11:45:44 AM

# Exercise 6a

Show that `f * unit = unit * f`

——————————

`(f * g) (x, xs)= ((bind f) . (bind g)) (x, xs)`

`bind f x = concat (map f x)`

`(f * unit) (x:xs)= bind f (bind unit (x:xs))= bind f (concat (map unit (x:xs)))= bind f (concat (map unit [x1, x2, x3, ...]))= bind f (concat ([[x1], [x2], [x3], ...]))= bind f [x1, x2, x3, ...]= concat (map f [x1, x2, x3, ...])= concat [f x1, f x2, f x3, ...]= [f x1, f x2, f x3, ...]`

`(unit * f) (x:xs)= ((bind unit) . (bind f)) (x:xs)= bind unit (bind f (x:xs))= bind unit (concat (map f (x:xs)))= bind unit (concat (map f [x1, x2, ...]))= bind unit (concat [f x1, f x2, ...])= bind unit [f x1, f x2, ...]= concat (map unit [f x1, f x2, ...])= concat [[f x1], [f x2], ...]= [f x1, f x2, ...]`

— Me@2015.07.20 09:00 PM

# Exercise 3.2

Show that `lift f * lift g = lift (f.g)`

——————————

The meaning of `f' * g'` should be `(bind f') . (bind g')` instead.

`f' * g' = (bind f') . (bind g')lift f = unit . ff' = lift f`

`(lift f * lift g) (x, xs)= (bind (lift f)) . (bind (lift g)) (x, xs)= bind (lift f) (bind (lift g) (x, xs))= bind (lift f) (gx, xs++gs)  where    (gx, gs) = (lift g) x`

``` = bind (lift f) (gx, xs++gs)  where    (gx, gs) = (g x, "") = bind (lift f) (g x, xs) = (fx, xs++fs)  where    (fx, fs) = (lift f) gx  = (fx, xs++fs)  where    (fx, fs) = (f gx, "") = (fx, xs)  where    (fx, fs) = (f (g x), "") ```

`= (f (g x), xs)`

`bind f' (gx,gs) = (fx, gs++fs)                  where                    (fx,fs) = f' gx`

``` bind (lift (f.g)) (x, xs)= (hx, xs++hs)  where    (hx, hs) = (lift (f.g)) x = (hx, xs++hs)  where    (hx, hs) = ((f.g) x, "") ```

`= ((f (g x)), xs)`

— Me@2015.07.19 11:04 PM

# Exercise Three

Show that `lift f * lift g = lift (f.g)`

——————————

`f' * g' = bind f' . g'lift f = unit . ff' = lift f`

`(lift f * lift g) (x, xs)= bind (lift f . lift g) (x, xs)= (hx, xs++hs)  where     (hx, hs) = lh x     lh x = (f' . g') x    f' = lift f    g' = lift g`

This line does not work, since `f'` cannot be applied to `(g' x)`, for the data types are not compatible:

`f' :: Float -> (Float, String)`

``` g' :: Float -> (Float, String) ```

`(g' x) :: (Float, String)`

The meaning of `f' * g'` should be `bind f' . (bind g')` instead.

— Me@2015-09-27 10:24:54 PM

# flatMap()

skybrian 70 days ago

If functional languages had called them the Mappable, Applicable, and FlatMappable interfaces, and used map(), apply(), and flatMap() instead of operators, it would have avoided a lot of confusion.

— Hacker News

bind ~ flatMap

— Me@2015-07-22 06:30:25 PM

2015.09.23 Wednesday ACHK

Monads in Haskell can be thought of as composable computation descriptions. The essence of monad is thus separation of composition timeline from the composed computation’s execution timeline, as well as the ability of computation to implicitly carry extra data, as pertaining to the computation itself, in addition to its one (hence the name) output, that it will produce when run (or queried, or called upon). This lends monads to supplementing pure calculations with features like I/O, common environment or state, etc.

2015.09.21 Monday ACHK

# Folding an infinite list

One big difference is that right folds work on infinite lists, whereas left ones don’t! To put it plainly, if you take an infinite list at some point and you fold it up from the right, you’ll eventually reach the beginning of the list. However, if you take an infinite list at a point and you try to fold it up from the left, you’ll never reach an end!

Learn You a Haskell for Great Good!

Note that the key difference between a left and a right fold is not the order in which the list is traversed, which is always from left to right, but rather how the resulting function applications are nested.

• With `foldr`, they are nested on “the inside”

`foldr f y (x:xs) = f x (foldr f y xs)`

Here, the first iteration will result in the outermost application of `f`. Thus, `f` has the opportunity to be lazy so that the second argument is either not always evaluated, or it can produce some part of a data structure without forcing its second argument.

• With `foldl`, they are nested on “the outside”

`foldl f y (x:xs) = foldl f (f x y) xs`

Here, we can’t evaluate anything until we have reached the outermost application of `f`, which we will never reach in the case of an infinite list, regardless of whether `f` is strict or not.

— edited Oct 24 ’11 at 12:21, answered Sep 13 ’11 at 5:17, hammar

— Stack Overflow

2015.08.23 Sunday by ACHK

# Exercise One

Write the function bind.

——————————

`bind f' (gx,gs) = (fx, gs++fs)                  where                    (fx,fs) = f' gx`

The meaning of `bind` here:

1. apply `f'` to the last result data `gx`, generating the new data `fx`; and

2. concat the last debug string, `gs`, to the string generating by `f'`, `fs`.

— Me@2015.07.19 10:25 PM

Generalize the bunny invasion example in the list monad chapter for an arbitrary number of generations.

— Wikibooks

——————————

`import Control.Monad`

``` generation = replicate 3gen n = foldr (<=<) return (replicate n generation) --- ```

`["bunny"] >>= gen n`

`m >>= g ≡ join (fmap g m)xs >>= f = concat (map f xs) -- for the List Monad`

`---`

`f >=> g= (\x -> f x) >>= g= concat (map g (\x -> f x))`
`--- `
`xs >>= f >=> gxs >>= (f >=> g)xs >>= ((\x -> f x) >>= g)(xs >>= f) >>= g`

``` ```

`xs >>= (return >=> g >=> h)((xs >>= return) >>= g) >>= h`
`--- `
`xs >>= return= concat (map f xs)= concat (map return xs)= concat (map return ["bunny"])= concat ([return "bunny"])= concat ([["bunny"]])= ["bunny"]`
`---`
`-- foldr f acc []     = acc-- foldr f acc (x:xs) = f x (foldr f acc xs)`

``` -- foldr (<=<) return (replicate n generation) ```

`foldr (<=<) return [h,g]= (<=<) h (foldr (<=<) return [g])= (<=<) h ((<=<) g (foldr return []))= (<=<) h ((<=<) g return)= h <=< g <=< return`
`---  `
`compose :: [b -> [b]] -> b -> [b]compose = foldr (<=<) return`

``` ```

`foldr (<=<) return (replicate n generation)= compose (replicate n generation)`

— Me@2015-07-08 11:29:40 PM

# Euler problem 30

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

`1634 = 1^4 + 6^4 + 3^4 + 4^48208 = 8^4 + 2^4 + 0^4 + 8^49474 = 9^4 + 4^4 + 7^4 + 4^4`

As `1 = 1^4` is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

——————————

`sum_5th_powers n = sum \$ map ((^5) . digitToInt) (show n)`

` -- sum_5th_powers 999999 == 354294-- sum_5th_powers 9999999 == 413343 `

For a number having more than 6 digits, the fifth powers of its digits cannot be the number itself. So we should consider only numbers with less than 7 digits.

`-- sum_5th_powers ______ <= 354294`

For the numbers not greater than 354294, the number whose sum_5th_powers can represent the largest number is …

When 2 –> 1, in exchange for 4 –> 9, we earn — we get 354199;
When 4 –> 3, in exchange for 1 –> 9, we earn — we get 353999;
When 5 –> 4, in exchange for 3 –> 9, we earn — we get 349999;
When 3 –> 2, in exchange for 4 –> 9, we earn — we get 299999.

So the maximum number sum_5th_powers can represent is …

`-- sum_5th_powers 299999 == 295277`

``` -- 295277-- 199999 -- sum_5th_powers 199999 == 295246 ```

`p30 = [n | n <- [10..m], n == sum_5th_powers n]    where m = 295246`

——————————

— Me@2015-07-06 08:42:07 PM

# Euler problem 27.2

——————————

` problem_27 = -(2*a-1)*(a^2-a+41)    where n = 1000          m = head \$ filter (\x -> x^2 - x + 41 > n) [1..]          a = m - 1  `

This is the “official” Haskell solution to Euler problem 27.

This solution is incomprehensible. The following hints are as far as I can get.

Prerequisite considerations:

`b` must be a prime number, since `x^2 + a*x + b` must be a prime number when `n=0`.

` a = m - 1 ` is a choice of the prime number `b` (in `x^2 + a*x + b`) just(?) smaller than 1000.

a == 32

(\x -> x^2 – x + 41) 31 == 971

Why not the prime number 997?

— Me@2015.06.14 08:53 AM

It is because 997 is not a prime number generated by the formula `x^2 - x + 41`.

— Me@2015-06-30 11:07:53 AM

`map (\x -> x^2 - x + 41) [0..40]`

is for generating 41 primes with the greatest Euler’s lucky number 41.

— Me@2015.06.14 08:34 AM

# Euler problem 27

`------------------------------`

``` primes = 2 : filter (null . tail . primeFactors) [3,5..] primeFactors n = factor n primes                 where                   factor n (p:ps)                       | p*p > n = [n]                       | n `mod` p == 0 = p : factor (n `div` p) (p:ps)                       | otherwise = factor n ps list_max (x:xs) = lmf x xs    where       lmf x []                    = x      lmf x xs | (x >= (head xs)) = lmf x (tail xs)               | otherwise        = lmf (head xs) (tail xs) elemInd y [] = -1elemInd y (x:xs) = ei 0 y (x:xs)                    where                       ei n y (x:xs)                           | (x == y)  = n                          | (null xs) = -1                          | otherwise = ei (n+1) y xs                                    b_list = takeWhile (<= 1000) primes isPrime x | x <= 1    = False          | otherwise = null \$ tail (primeFactors x) cPrimeLen [a, b] = [m, a, b]    where m = length \$ takeWhile (== True) \$ map (isPrime . (\n -> n^2 + a*n + b)) [0..] p27_list = [cPrimeLen [a, b] | a <- [-n..n], b <- b_list]    where n = 1000 p27_n = map head p27_list p27 = p27_list !! (elemInd (list_max p27_n) p27_n) -- 71, a == -61, b == 971 ```

`------------------------------`

— Me@2015-06-19 10:01:22 PM

# Euler problem 26

——————————

``` rems n d xs     | (r == 0)    = xs ++     | (elem r xs) = xs ++ [r] ++ [-1]    | otherwise   = (rems (10*r) d (xs ++ [r]))    where r = n `rem` d remainders n d = rems n d [] recur_cyc (x:xs)     | (elem 0 ys)          = 0    | (not (elem (-1) ys)) = -2            | (not (elem x xs))    = recur_cyc xs                              | otherwise            = (length ys) - 2    where ys = (x:xs) elemInd y [] = -1elemInd y (x:xs) = ei 0 y (x:xs)                    where                       ei n y (x:xs)                           | (x == y)  = n                          | (null xs) = -1                          | otherwise = ei (n+1) y xs                                     list_max [x] = xlist_max (x:xs) = max x \$ list_max xs recur_list = map (\x -> (recur_cyc (remainders 1 x))) [1..1000] p26 = 1 + (elemInd (list_max recur_list) recur_list) ```

`-- 983`

——————————

— Me@2015-06-05 03:25:44 PM

# Euler problem 24

`------------------------------`

``` deleteNth n xs | n>0 = take (n-1) xs ++ drop n xs removeItem x xs = filter (/= x) xs sub_lexico x [] = [[]] sub_lexico x xs = map (x:) (lexico (removeItem x xs)) merge_sub_lexico [] = [] merge_sub_lexico (x:xs) = x ++ (merge_sub_lexico xs) lexico [] = [[]] lexico xs = (merge_sub_lexico (map (\x -> (sub_lexico x xs)) xs)) p24 = (lexico [0,1,2,3,4,5,6,7,8,9]) !! (1000000 - 1) ```

`------------------------------`

— Me@2015-05-27 12:09:33 PM

# Learn Physics by Programming in Haskell

Learning functional programming and partially applying functions to other functions and such helped me understand tensors a lot better, since that’s basically what contraction is doing. It’s nice to see that the approach can be taken further.

— Snuggly_Person

I also think Haskell and some similar languages (especially Idris) have a great conceptual synergy with physics.

In physics too we strive to express things in ways that strip out extraneous details as much as possible. Haskell really embraces this concept in the sense that you write functions essentially by writing equations. You don’t describe all the mechanical steps to produce an output, you just write down the ‘invariant content’ of the function.

— BlackBrane

2015.03.29 Sunday ACHK

# Functional programming 6.3

Just because a functional language is functional ([maybe] even completely pure like Haskell!), it doesn’t mean that programs written in that language must be pure when [run].

Haskell’s approach, for example, when dealing with side-effects, can be explained rather simply: Let the whole program itself be pure (meaning that functions always return the same values for the same arguments and don’t have any side effect), but let the return value of the `main` function be an action that can be [run].

— answered Dec 6 ’11 at 21:32, dflemstr

— Stack Overflow

2013.09.03 Tuesday ACHK