Category Archives: Haskell

Haskell/Understanding monads/IO, Exercises 2

Posted on by

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

Euler problem 30

Posted on by

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

-- 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

Euler problem 27.2

Posted on by 

p_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.

When 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

.

The code

l = 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

λ> :set +s
λ> p_27
[-59231,-61,971]
(0.00 secs, 113,624 bytes)
λ>

— Me@2025-03-24 01:20:37 PM

.

.

2015.07.01 Wednesday (c) All rights reserved by ACHK

Euler problem 27

Posted on by 

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

Euler problem 26

Posted on by

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

Euler problem 24

Posted on by

Haskell

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

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

2015.05.27 Wednesday (c) All rights reserved by ACHK

Learn Physics by Programming in Haskell

Posted on by

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

Posted on by

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

Functional programming 6.2

Posted on by

The I/O monad

In a purely functional language, such as Haskell, functions cannot have any externally visible side effects. Although a function cannot directly cause a side effect, it can construct a value describing a desired side effect, that the caller should apply at a convenient time. In the Haskell notation, a value of type IO a represents an action that, when performed, produces a value of type a.

We can think of a value of type IO as a function that takes as its argument the current state of the world, and will return a new world where the state has been changed according to the function’s return value. The state created in this way can be passed to another function, thus defining a series of functions which will apply in order as steps of state changes. This process is similar to how a temporal logic represents the passage of time using only declarative propositions.

— Wikipedia on Monad (functional programming)

2012.08.22 Wednesday ACHK

Functional programming 6

Posted on by

A central concept in functional languages is that the result of a function is determined by its input, and only by its input. There are no side-effects! 

— Why Haskell matters

My question is, if a function makes changes only within its local environment, and returns the result, how can it interact with a database or a file system? By definition, wouldn’t that be accessing what is in effect a global variable or global state?

What is the most common pattern used to get around or address this?
   
— edited Dec 7 ’11 at 2:10, Matt Fenwick
   
— asked Dec 6 ’11 at 20:18, juwiley

The most common pattern for dealing with side-effects and impurity in functional languages is:

  •     be pragmatic, not a purist
  •     provide built-ins that allow impure code and side-effects
  •     use them as little as possible!

Examples:

  •     Lisp/Scheme: set!
  •     Clojure: refs, and using mutating methods on java objects
  •     Scala: creating variables with var
  •     ML: not sure of specifics, but Wikipedia says it allows some impurity

Haskell cheats a little bit — its solution is that for functions that access the file system, or the database, the state of the entire universe at that instant, including the state of the filesystem/db, will be passed in to the function.(1) Thus, if you can replicate the state of the entire universe at that instant, then you can get the same results twice from such a function. Of course, you can’t replicate the state of the entire universe at that instant, and so the functions return different values …

But Haskell’s solution, IMHO, is not the most common.

(1) Not sure of the specifics here. Thanks to CAMcCann for pointing out that this metaphor is overused and maybe not all that accurate.   

— edited Dec 7 ’11 at 2:11

— answered Dec 6 ’11 at 22:00, Matt Fenwick

— Stack Overflow

2012.08.12 Sunday ACHK

The “$” Operator

Posted on by

Next to the “.” operator there is another function-oriented operator that you’ll see often in Haskell code. This is the function application operator and it’s defined like this:

f $ x = f x

Weird right? Why does Haskell have this?

In Haskell, normal function application has a higher precedence than any other operator and it’s left-associative:

f g h j x == (((f g) h) j) x

Conversely, “$” has the lowest precedence of all operators and it’s right-associative:

f $ g $ h $ j $ x == f (g (h (j x)))

Using “$” can make Haskell code more readable as an alternative to using parentheses. It has other uses too, more on that later.

— Using the Dropbox API from Haskell

— by Rian on January 02, 2012

2012.05.31 Thursday ACHK

Folds, maps, and filters

Posted on by

Why use folds, maps, and filters?

A quick glance reveals that adler32_foldl isn’t really any shorter than adler32_try2. Why should we use a fold in this case? The advantage here lies in the fact that folds are extremely common in Haskell, and they have regular, predictable behavior.

This means that a reader with a little experience will have an easier time understanding a use of a fold than code that uses explicit recursion. A fold isn’t going to produce any surprises, but the behavior of a function that recurses explicitly isn’t immediately obvious.

— Chapter 4: Functional programming

— Real World Haskell

— by Bryan O’Sullivan, Don Stewart, and John Goerzen

2012.05.20 Sunday ACHK

Curry–Howard correspondence, 3

Posted on by

Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, “a function is a first-class citizen” of the programming language. As a functional programming language, the primary control construct is the function. The language is rooted in the observations of Haskell Curry and his intellectual descendants, that “a proof is a program; the formula it proves is a type for the program“.

— Wikipedia on Haskell (programming language)

2012.02.07 Tuesday ACHK

Literate programming 2

Posted on by

The Haskell programming language has native support for semi-literate programming, inspired by CWEB but with a simpler implementation. When aiming for TeX output, one writes a plain LaTeX file where source code is marked by a given surrounding environment; LaTeX can be set up to handle that environment, while the Haskell compiler looks for the right markers to identify Haskell statements to compile, removing the TeX documentation as if they were comments. However, as described above, this is not literate programming in the sense intended by Knuth. Haskell’s functional, modular nature makes literate programming directly in the language somewhat easier, but it is not nearly as powerful as one of the WEB tools where “tangle” can reorganize in arbitrary ways.

— Wikipedia on Literate programming

2012.01.01 Sunday ACHK

Batteries included

Posted on by

The Haskell Platform is a collection of software-packages, tools and libraries, which is to create a common platform for using and developing applications in Haskell. With the Haskell Platform, Haskell follows the same principle as Python: “Batteries included”.

— Wikipedia on Haskell Platform

The quality of a programming language itself is only one component in the ability of application writers to get the job done. Programming languages can succeed or fail based on the breadth and quality of their library collection.

— Haskell: Batteries Included

— Duncan Coutts, Isaac Potoczny-Jones and Don Stewart

2011.06.20 Monday ACHK

Haskellers’ loops

Posted on by

Haskellers never use loops – Instead, they either use recursion to do looping, or they use functions like map that take other functions as parameters.

— Conrad Barski, M.D.

2011.05.22 Sunday ACHK

Type inference

Posted on by

While strong, static typing makes Haskell safe, type inference makes it concise. The result is potent: we end up with a language that’s both safer than popular statically typed languages, and often more expressive than dynamically typed languages. This is a strong claim to make, and we will back it up with evidence throughout the book.

— Real World Haskell

— by Bryan O’Sullivan, Don Stewart, and John Goerzen

2011.01.09 Sunday ACHK