Euler problem 12.2

Posted on May 4, 2023 by rpflee

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

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

groupFactors :: [Integer] -> [[Integer]]
groupFactors = gf []
  where
    gf acc lst
      | null lst = reverse acc
      | null acc = gf [[p,1]] ps
      --
      | p == head (head acc) =
        gf ([p, head (tail (head acc)) + 1]:tail acc) ps
      --  
      | otherwise = gf ([p,1]:acc) ps
      where
        p = head lst
        ps = tail lst
        
nDiv :: Integer -> Integer
nDiv n = product (map ((1+) . head . tail)
                  (groupFactors (primeFactors n)))

fm :: Integer -> Integer -> Integer
fm m n
  | triDiv n > m = n*(n+1) `div` 2
  | otherwise = fm m (n+1)
  where
    triDiv n
      | even n = nDiv (n `div` 2)*nDiv (n+1)
      | otherwise = nDiv n*nDiv ((n+1) `div` 2)

λ> :set +s
λ> fm 500 1
76576500
(0.20 secs, 199,313,728 bytes)
λ>

— Me@2023-05-04 09:51:19 AM

Euler problem 10.2

Posted on February 26, 2023 by rpflee

Find the sum of all the primes below two million.

removeIf :: (a -> Bool) -> [a] -> [a]
removeIf p = filter (not . p)

sieveIter :: Integral a => [a] -> [a] -> [a]
sieveIter [] (x:xs) = x:xs
sieveIter (x:xs) acc
  | x^2 > last (x:xs) = reverse acc++(x:xs)
  | otherwise = sieveIter xss (x:acc)
  where
    xss = removeIf (\n -> n `mod` x == 0) xs

primeList :: Integral a => [a] -> [a]
primeList xs = sieveIter xs []

pL :: [Integer]
pL = primeList [2..2000000]

f :: Integer
f = sum (takeWhile (< 2000000) pL)

— colorized by palette fm

— Me@2023-02-25 12:35:57 PM

Direct from Dell

Posted on December 11, 2022 by rpflee

Euler problem 9.2

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

g p =
  [ [a, b, c]
    | m <- [2 .. limit],
      n <- [1 .. (m - 1)],
      let a = m ^ 2 - n ^ 2,
      let b = 2 * m * n,
      let c = m ^ 2 + n ^ 2,
      a + b + c == p
  ]
  where
    limit = floor . sqrt . fromIntegral $ p

— based on Haskell official

Euclid’s formula is a fundamental formula for generating Pythagorean triples given an arbitrary pair of integers $m$ and $n$ with $m > n > 0$ . The formula states that the integers

$\displaystyle{ a=m^{2}-n^{2},\ \,b=2mn,\ \,c=m^{2}+n^{2}}$

form a Pythagorean triple. The triple generated by Euclid’s formula is primitive if and only if $m$ and $n$ are coprime and one of them is even. When both $m$ and $n$ are odd, then $a$ , $b$ , and $c$ will be even, and the triple will not be primitive; however, dividing $a$ , $b$ , and $c$ by 2 will yield a primitive triple when $m$ and $n$ are coprime.

Every primitive triple arises (after the exchange of $a$ and $b$ , if $a$ is even) from a unique pair of coprime numbers $m$ , $n$ , one of which is even.

— Wikipedia on Pythagorean triple

— Me@2022-12-10 09:57:27 PM

Importance, 2.2

Posted on November 19, 2022 by rpflee

Euler problem 8.2

import Data.Char

max13 lst = max13n lst 0
  where
    max13n lst n | (length lst) < 13 = n
                 | n > take13        = max13n (tail lst) n
                 | otherwise         = max13n (tail lst) take13
      where
        take13 = product (take 13 lst)

str <- readFile "n.txt"

max13 (map (fromIntegral . digitToInt) . concat . lines $ str)

— Me@2022-11-19 12:04:41 PM

Euler problem 6.2

Posted on November 4, 2022 by rpflee

1960s

— ShutUpImStillTalking

f = (sum [1..100])^2 - sum (map (^2) [1..100])

— colorized by palette fm

— Me@2022-11-03 05:55:51 PM

The Sixth Sense, 2.2

Posted on October 23, 2022 by rpflee

Euler problem 5.2 | Folding an infinite list, 2

f = foldr1 lcm [1..20]

Most problems on Project Euler can be solved in three ways:

with brute-force
with an algorithm that solves a more general problem
with a smart solution that requires pencil and paper at most

If you’re interested in a nice solution rather than fixing your code, try concentrating on the last approach …

— edited Oct 8, 2016 at 8:57

— huwr

— answered Dec 27, 2011 at 14:33

— Philip

— Stack Overflow

Euler problem 4.2

Posted on October 11, 2022 by rpflee

Find the largest palindrome made from the product of two 3-digit numbers.

g = [(y, z, y*z) | y<-[100..999], z<-[y..999], f==y*z]
    where
      f = maximum [x | y<-[100..999], z<-[y..999],
                   let x=y*z, let s=show x, s==reverse s]

— based on Haskell offical

— Me@2022-10-10 10:09:53 PM

SimCity 2013

Posted on September 28, 2022 by rpflee

Euler problem 3.4

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

f = last (primeFactors 600851475143)

— Haskell offical

— Me@2022.09.28 11:44:20 AM

Haskell mode, 2

Posted on September 21, 2022 by rpflee

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

Haskell mode

Posted on August 20, 2022 by rpflee

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

Functional programming jargon in plain English

Posted on July 17, 2022 by rpflee

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 $\displaystyle{f\colon (X\times Y\times Z)\to N}$ and $\displaystyle{a\in X}$ then

$\displaystyle{{\text{curry}}({\text{partial}}(f)_{a})(y)(z)={\text{curry}}(f)(a)(y)(z)}$

or simply

$\displaystyle{{\text{partial}}(f)_{a}={\text{curry}}_{1}(f)(a)}$

where $\displaystyle{{\text{curry}}_{1}}$ curries $\displaystyle{f}$ ‘s first parameter.

— Wikipedia on Currying

2022.07.16 Saturday ACHK

Functors, Applicatives, And Monads In Pictures

Posted on February 16, 2018 by rpflee

d_2018_02_16__16_21_28_PM_

https://web.archive.org/web/20180124053031/http://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html

2018.02.16 Friday ACHK

Exercise 6.2

Posted on January 30, 2016 by rpflee

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

Exercise 6a (Corrected version)

Posted on October 15, 2015 by rpflee

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

Real World Haskell

Posted on October 8, 2015 by rpflee

— Me@2015-10-08 12:25:54 PM

2015.10.08 Thursday ACHK

Exercise 6a

Posted on October 6, 2015 by rpflee

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

Exercise 3.2

Posted on October 2, 2015 by rpflee

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

Functional programming 7

Posted on October 1, 2015 by rpflee

Functional programming

~ Timeless programming

— Me@2015-09-29 12:50:45 PM

Exercise Three

Posted on September 27, 2015 by rpflee

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

flatMap()

Posted on September 23, 2015 by rpflee

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

Physics Town

continues

Category Archives: Haskell

Euler problem 12.2

Euler problem 10.2

Direct from Dell

Importance, 2.2

Euler problem 6.2

The Sixth Sense, 2.2

Euler problem 4.2

SimCity 2013

Haskell mode, 2

Haskell mode

Functional programming jargon in plain English

Functors, Applicatives, And Monads In Pictures

Exercise 6.2

Exercise 6a (Corrected version)

Real World Haskell

Exercise 6a

Exercise 3.2

Functional programming 7

Exercise Three

flatMap()