Euler Problem 101 - Optimum polynomial

Question

Here is my solution in Haskell for the Euler problem #101. It relies on building a specific base of polynomes given the values we want to fit (memories of my linear algebra courses from a long time ago). The algorithm is quite fast but as a new Haskell programmer, I'd like your opinion on what could be done to improve this code, be it either Haskell conventions, style or optimization.

module Polynome.Optimal where

-- given a list, returns a polynome of degree length xs which is zero on all element of the list
getPolynome :: [Int] -> Int -> Int
getPolynome = foldr f (const 1) where
    f x acc n = (n-x) * acc n

getLists :: [Int] -> [[Int]]
getLists xs = zipWith (const . ($ xs)) (map remove [0..]) xs

remove :: Int -> [Int] -> [Int]
remove n = go 0
    where go _ [] = []
          go i (y:ys) | i == n = ys
                       | otherwise = y: go (i+1) ys

getBase :: [Int] -> [Int -> Int]
getBase xs = map getPolynome $ getLists xs

scalePolynome :: Int -> Int -> (Int -> Int) -> Int -> Int
scalePolynome x y p t = (p t * y) `div` p x

getPolyFit :: [(Int,Int)] -> Int -> Int
getPolyFit vs = foldr f (const 0) ls where
    (xs, _) = unzip vs
    bs = getBase xs
    ls = zipWith (\ (x,y) b -> scalePolynome x y b) vs bs
    f b acc t = b t + acc t

exValues :: [(Int,Int)]
exValues = [(i, u i) | i <- [1..], let u t = 1- t + t^2 - t^3 + t^4 - t^5 + t^6 - t^7 + t^8 - t^9 +t^10]

getPartialFit :: Int -> [(Int,Int)] -> Int -> Int
getPartialFit n = getPolyFit . take n


getFit :: [(Int,Int)] -> (Int -> Int) -> Int
getFit vs p = snd (head (dropWhile predicate $ zip vs ps)) where
    ps = map (\(x, _) -> p x) vs
    predicate ((x, y), p) = p == y

-- result 10 exValues returns the solution to problem 101
result :: Int -> [(Int,Int)] -> Int
result n values = sum fits where
    bops = map (($ values) . getPartialFit) [1..n]
    fits = map (getFit values) bops

Answer 1

I know it's hard to name things, but try to come up with more descriptive names for your functions. As a general rule, I would avoid using the prefix get... for pure functions. It's just noise and doesn't help the reader understand what the function is. In Haskell we try to describe what things are and less how things are done.

Some names which I think are somewhat better...

zeroPoly :: [Int] -> (Int -> Int)

e.g. zeroPoly [1,2,3] is a polynomial which is zero on 1, 2 and 3.

remove1 :: [a] -> [[a]]

e.g. remove1 as is all the ways of removing one element from the list as. Also, using the polymorphic signature alerts the reader that the function isn't specific to Ints.

I would also introduce a type alias:

type Poly = Int -> Int

so you can write the signature of scalePolynome (and other functions) as:

scalePolynome :: Int -> Int -> Poly -> Poly

which helps to describe better what it is doing. Anywhere you can use the alias Poly instead of Int -> Int will help the reader.

In fact, I would even write the signature this way:

scalePolynome :: (Int,Int) -> Poly -> Poly

since you use (x,y) tuples elsewhere for points on the function.

You should be careful about using div here. Are you sure that with your basis polynomials you'll always get a integral result? To be safe you might have to perform the calculations with Rationals.

Instead of getBase I would probably call the function basisPolynomials - again, just avoid the prefix get....

Finally, note that your getList and remove functions can be written in terms of the inits and tails functions from Data.List:

import Data.List

remove1 :: [a] -> [[a]]
remove1 as = zipWith (++) (inits as) (tail $ tails as)