Euler problem 3.3
.
The goal of this blog post is to install an advanced Haskell mode, called LSP mode, for Emacs.
.
1. Open the bash terminal, use the following commands to install the three packages:
sudo apt-get install elpa-haskell-mode sudo apt-get install elpa-yasnippet sudo apt-get install elpa-which-key
.
2. Read and follow the exact steps of my post titled “Haskell mode“.
.
.
— Me@2022.09.20 12:49:29 PM
.
.
2022.09.21 Wednesday (c) All rights reserved by ACHK
The goal of this blog post is to install an advanced Haskell mode, called LSP mode, for Emacs.
0. In this tutorial, you will need to go to the official website of NixOS and that of MELPA (Milkypostman’s Emacs Lisp Package Archive). Make sure that both websites are the real official ones. Any instructions from an imposter website can get your machine infected with malware.
1. Assuming your computer OS is Ubuntu 20.04 or above, go to the NixOS official website. Follow the instructions to install the Nix package manager (not the NixOS) onto your OS. Choose the “single-user installation” method.
2. On the NixOS official website, click the magnifying glass at the top right corner to reach the package search engine.
3. Search “haskell language server” and then copy its installation command.
nix-env -iA nixpkgs.haskell-language-server
4. Run the command in the bash terminal to install the Haskell Language Server.
.
5. Search “stack” on the package search engine.
6. Run its installation command
nix-env -iA nixpkgs.stack
to install the Haskell Tool Stack.
7. Search “ghc” on the package search engine.
8. Run its installation command
nix-env -iA nixpkgs.ghc
to install the Glasgow Haskell Compiler.
.
9. Reboot your computer.
This step is needed for triggering the OS to recognize the Nix package manager setup.
.
10. Go to MELPA package manager’s official website. Follow the instructions to install “Melpa”, not “Melpa Stable”.
11. Open the Emacs editor. Click "Options" and then "Manage Emacs Packages".
Install the following packages. For each of them, make sure that you have chosen the source archive as “melpa“. Versions from other sources would not work.
| company | Modular text completion framework | |||
| flycheck | On-the-fly syntax checking | |||
| lsp-haskell | Haskell support for lsp-mode | |||
| lsp-mode | LSP mode | |||
| lsp-ui | UI modules for lsp-mode |
12. Open Emacs’ initialization file, which has the filename
.emacs
Its location should be
~/.emacs
13. Add the following code to the file.
;;;;;;;;;;;;;;;;;;;;;;;;;;
(require 'company)
(require 'flycheck)
(require 'lsp-ui)
;;;;;;;;;;;;;;;;;;;;;;;;;;
(require 'lsp)
(add-hook 'haskell-mode-hook #'lsp)
(add-hook 'haskell-literate-mode-hook #'lsp)
(save-place-mode 1)
;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun haskell-and-go-back ()
(interactive)
(haskell-process-load-file)
(windmove-up))
(global-set-key
(kbd "C-n")
'haskell-and-go-back)
;;;;;;;;;;;;;;;;;;;;;;;;;;
14. Close the Emacs program.
.
15. Create a dummy Haskell source code file named “test.hs”.
16. Use Emacs to open it.
17. You should see this message:
18. Select one of the first 3 answers. Then you can start to do the Haskell source code editing.
19. To compile your code, hold the Ctrl key and press n.
Ctrl+n
— Me@2022-08-18 05:22:02 PM
.
.
2022.08.20 Saturday (c) All rights reserved by ACHK
mjburgess 11 days ago | next [–]
These definitions don’t really give you the idea, rather often just code examples..
“The ideas”, in my view:
| Monoid | = | units that can be joined together |
| Functor | = | context for running a single-input function |
| Applicative | = | context for multi-input functions |
| Monad | = | context for sequence-dependent operations |
| Lifting | = | converting from one context to another |
| Sum type | = | something is either A or B or C… |
| Product type | = | a record |
| = | something is both A and B and C | |
| Partial application | = | defaulting an argument to a function |
| Currying | = | passing some arguments later |
| = | rephrasing a function to return a functions of n-1 arguments when given 1, st. the final function will compute the desired result | |
| EDIT: Context | = | compiler information that changes how the program will be interpreted (, executed, compiled,…) |
| Eg., context | = | run in the future, run across a list, redirect the i/o, … |
— Functional programming jargon in plain English
— Hacker News
.
Currying and partial function application are often conflated. One of the significant differences between the two is that a call to a partially applied function returns the result right away, not another function down the currying chain; this distinction can be illustrated clearly for functions whose arity is greater than two.
.
Partial application can be seen as evaluating a curried function at a fixed point, e.g. given 
or simply
where 
— Wikipedia on Currying
.
.
2022.07.16 Saturday ACHK
You Could Have Invented Monads! (And Maybe You Already Have.)
f :: a -> b
f' :: a -> m a
unit :: 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 …
— Wikibooks on Haskell/Understanding monads
— Me@2016-01-26 03:05:50 PM
2016.01.30 Saturday (c) All rights reserved by ACHK
You Could Have Invented Monads! (And Maybe You Already Have.)
Show that f' * unit = unit * f' = bind f'
——————————
f :: a -> b
f' :: a -> m a
unit :: a -> m a
lift f = unit . f
f' = 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
2015.10.15 Thursday (c) All rights reserved by ACHK
You Could Have Invented Monads! (And Maybe You Already Have.)
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
2015.10.06 Tuesday (c) All rights reserved by ACHK
You Could Have Invented Monads! (And Maybe You Already Have.)
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 . f
f' = 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
2015.10.02 Friday (c) All rights reserved by ACHK
Functional programming
~ Timeless programming
— Me@2015-09-29 12:50:45 PM
2015.10.01 Thursday (c) All rights reserved by ACHK
You Could Have Invented Monads! (And Maybe You Already Have.)
Show that lift f * lift g = lift (f.g)
——————————
f' * g' = bind f' . g'
lift f = unit . f
f' = 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
2015.09.27 Sunday (c) All rights reserved by ACHK
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.
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.
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
generation = replicate 3
gen n = foldr (<=<) return (replicate n generation)
---
["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 (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
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^4As
1 = 1^4is 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
2015.07.07 Tuesday (c) All rights reserved by ACHK
Haskell
——————————
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
2015.07.01 Wednesday (c) All rights reserved by ACHK
Haskell
------------------------------
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 [] = -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
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
2015.06.20 Saturday (c) All rights reserved by ACHK
Haskell
——————————
rems n d xs
| (r == 0) = xs ++ [0]
| (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 [] = -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
list_max [x] = x
list_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
2015.06.05 Friday (c) All rights reserved by ACHK
Physics Town 
You must be logged in to post a comment.