Functors, Applicatives, and Monads

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.

— Haskell Official Wiki

2015.09.21 Monday ACHK

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

You Could Have Invented Monads! (And Maybe You Already Have.)

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

2015.07.27 Monday (c) All rights reserved by ACHK

Haskell

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

— Wikibooks

——————————

import Control.Monad

["bunny"] >>= gen n

Additional notes:

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 >=> g
xs >>= (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 [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

2015.07.15 Wednesday (c) All rights reserved by ACHK

Haskell

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^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 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

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

——————————

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

2015.07.07 Tuesday (c) All rights reserved by ACHK

primes :: [Int]
primes = 2 : filter (null . tail . primeFactors) [3,5..]

primeFactors :: Int -> [Int]
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

listMax :: Ord a => [a] -> a
listMax (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 :: (Num a, Eq t) => t -> [t] -> a
elemInd y [] = -1
elemInd 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

bList :: [Int]
bList = takeWhile (<= 1000) primes

isPrime :: Int -> Bool
isPrime x | x <= 1    = False
          | otherwise = null $ tail (primeFactors x)

cPrimeLen :: [Int] -> [Int]
cPrimeLen [a, b] = [m, a, b]
    where
      m = length $ takeWhile (isPrime . (\n -> n^2 + a*n + b)) [0..]

p27List :: [[Int]]
p27List = [cPrimeLen [a, b] | a <- [-n..n], b <- bList]
  where
    n = 1000

p27n :: [Int]
p27n = map head p27List

p27 :: [Int]
p27 = p27List !! elemInd (listMax p27n) p27n

λ> :set +s
λ> p27
[71,-61,971]
(2.97 secs, 3,146,880,176 bytes)
λ> 

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

— Me@2025-02-20 04:34:12 PM

.

.

2015.06.20 Saturday (c) All rights reserved by ACHK

Haskell

——————————

-- 983

——————————

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

2015.06.05 Friday (c) All rights reserved by ACHK

Haskell

------------------------------

------------------------------

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

2015.05.27 Wednesday (c) All rights reserved by ACHK