Euler Project 3 - Haskell
I am working on Project Euler problems in Haskell. I have a solution for problem 3 below, I tested it on small amounts and it works, however due to the brute force implementation, outputting all prime numbers is exponentially slow at first for large numbers.
-- Project Euler 3
module Main
where
import System.IO
import Data.List
main = do
hSetBuffering stdin LineBuffering
putStrLn "This program returns the prime factors of a given integer"
putStrLn "Please enter a number"
nums <- getPrimes
putStrLn "The prime factors are: "
print (sort nums)
getPrimes = do
userNum <- getLine
let n = read userNum :: Int
let xs = [2..n]
return $ getFactors n (primeGen xs)
--primeGen :: (Integral a) => [a] -> [a]
primeGen [] = []
primeGen (x:xs) =
if x >= 2
then x:primeGen (filter (\n->n`mod` x/=0) xs)
else 1:[2]
--getFactors
getFactors :: (Integral a) => a -> [a] -> [a]
getFactors n xs = [ x | x <- xs, n `mod` x == 0]
I've reviewed the solution here and can see how it is optimized by the first guard in factor
. What I don't understand is this:
primes = 2 : filter ((==1) . length . primeFactors) [3,5..]
In particular, the first argument filter
.
((==1) . length . primeFactors)
As primeFactors itself a function, I don't understand how it is used in this context. Can anyone explain what is going on here please?
source to share
If you opened ghci
a command prompt and type
Prelude> :t filter
You will receive output
filter :: (a -> Bool) -> [a] -> [a]
This means it filter
takes 2 arguments.
-
(a -> Bool)
is a function that takes one input and returnsBool
. -
[a]
is a list of any type since it is the same type from the first argument.
filter
will iterate over each item in the list of its second argument and apply it to the function that is its first argument. If the first argument returns True
, it is added to the resulting list.
Again, in ghci
if you typed
Prelude> :t (((==1) . length . primeFactors))
You should get
(((==1) . length . primeFactors)) :: a -> Bool
(==1)
- partially applied function.
Prelude> :t (==)
(==) :: Eq a => a -> a -> Bool
Prelude> :t (==1)
(==1) :: (Eq a, Num a) => a -> Bool
Only one argument is required instead of two.
Meaning this together, it will take one argument and return a boolean.
How it works:
-
primeFactors
will take one argument and calculate the results that are[Int]
. -
length
will take this list and calculate the length of the list and returnInt
-
(==1)
will see if the values returned matchlength
1
.
If the length is a list 1
, it means it is a prime number.
source to share
Expression
filter ((==1) . length . primeFactors) [3,5..]
filters the list [3, 5..]
using a function (==1) . length . primeFactors
. This notation is usually called dot free, not because it has no dots .
, but because it has no explicit arguments (called "dots" in some mathematical contexts).
.
is actually a function and, in particular, performs the function of composition. If you have two functions f
and g
, then f . g = \x -> f (g x)
that is it! The precedence of this operator allows many functions to be combined quite smoothly, so if you have f . g . h
, it's the same as \x -> f (g (h x))
. When you have many functions to combine with each other, the composition operator is very useful.
So, in this case, you are linking functions (==1)
, length
and primeFactors
. (==1)
is a function through what's called operator sections, which means that you provide an argument to one side of the operator, and this results in a function that takes one argument and applies it to the other side. Other examples and their equivalent lambdas are
(+1) => \x -> x + 1
(==1) => \x -> x == 1
(++"world") => \x -> x ++ "world"
("hello"++) => \x -> "hello" ++ x
If you want, you can rewrite this expression with a lambda:
(==1) . length . primeFactors => (\x0 -> x0 == 1) . length . primeFactors
=> (\x1 -> (\x0 -> x0 == 1) (length (primeFactors x1)))
Or a little cleaner with the operator $
:
(\x1 -> (\x0 -> x0 == 1) $ length $ primeFactors x1)
But this is still much more verbose than just
(==1) . length . primeFactors
One thing to keep in mind is the type signature for .
:
(.) :: (b -> c) -> (a -> b) -> a -> c
But I think it looks better with some extra parentheses:
(.) :: (b -> c) -> (a -> b) -> (a -> c)
This makes it clearer that this function performs two other functions and returns the third. Pay attention to the order of the type variables in this function. The first argument .
is a function (b -> c)
and the second is a function (a -> b)
. You can think of it as right-to-left, not right-to-left, which we are used to in most OOP languages (sort of myObj.someProperty.getSomeList().length()
). We can get this functionality by defining a new operator that has the reverse order of its arguments. If we're using the F # convention, our operator is called |>
:
(|>) :: (a -> b) -> (b -> c) -> (a -> c)
(|>) = flip (.)
Then we could write it like
filter (primeFactors |> length |> (==1)) [3, 5..]
And you can think of it |>
as an arrow feeding the result of one function into the next.
source to share