Can't index into a list constructed by a recursive function - list

I have a function getN' that is supposed to construct a list of n elements recursively, however I think I'm doing something wrong because I can't index into it and the output looks unexpected:
getN' : (Double -> Double -> Double) -> Double -> Double -> Double -> Int -> List Double
getN' f dt t0 y0 0 = []
getN' f dt t0 y0 n = rk4' :: getN' f dt (t0+dt) rk4' (n-1) where
rk4' = rk4 f dt t0 y0
The output of getN' f 0.1 0 1 100 is:
1.0050062486962987 :: getN' f 0.1 0.1 1.0050062486962987 99 : List Double
Which looks unfamiliar to me. Specifically the syntax head::tail is familiar, but Idris usually prints out the entire result in the REPL, which suggests something isn't right in this instance.
The output of index 0 $ getN' f 0.1 0 1 100 is:
(input):1:9:When checking argument ok to function Prelude.List.index:
Can't find a value of type
InBounds 0 (getN' f 0.1 0.0 1.0 100)
What am I doing/getting wrong?

getN' isn't total, so the REPL doesn't evaluate the recursive call (as it could loop forever). Set %default total or total getN' : … to get a warning from the compiler, or check in the REPL with :total getN'. Idris can't reason about Int, and in this particular case, getN' f 0.1 0 1 -1 wouldn't stop.
If you replace Int with Nat it works (with 0 to Z, n to (S n) and n - 1 to n). From another answer: The compiler does only know that subtracting 1 from an Integer results to an Integer, but not which number exactly (unlike when doing it with a Nat). This is because arithmetic with Integer, Int, Double and the various Bits are defined with primary functions like prim__subBigInt.
Why index fails: it needs a proof InBounds k xs, that the list has at least k elements. In Haskell, !! is weaker, and thus can crash at runtime: (getN' f 0.1 0 1 100) !! 101 would compile, but will throw an exception. This can't happen in Idris:
>:t index
Prelude.List.index : (n : Nat) -> (xs : List a) -> {auto ok : InBounds n xs} -> a
>:printdef InBounds
data InBounds : Nat -> List a -> Type where
InFirst : InBounds 0 (x :: xs)
InLater : InBounds k xs -> InBounds (S k) (x :: xs)
auto means, that the compiler tries to search for a proof ok : InBounds n xs. But, again, it doesn't evaluate getN' …, so it doesn't find (or even searches) for a proof. That's the error you are getting: Can't find a value of type InBounds …

Related

Multiply all numbers in a list - Haskell [duplicate]

This question already has an answer here:
product of list iteratively
2 answers
I'm really new to haskell and would like to multiply all numbers in an array. For example.:
Array:
[3,2,4] //3*2*4
Output
24
Thanks, any help is greatly appreciated.
There are a number of ways of doing it in Haskell.
For instance, you could use:
product [3,2,4]
or equivalently
foldr (*) 1 [3,2,4]
or recursively:
prod [] = 1
prod (x : xs) = x * prod xs
Function foldr is the so called list catamorphism. To understand foldr we need to first understand list constructors. In Haskell, [3,2,4] is a syntax sugar for 3 : 2 : 4 : [], where : is list-cons constructor and [] is the empty list. Application foldr f v replaces every occurrence of : in a list by function f and the empty list for v. Its definition is as follows:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v -- equation 1
foldr f v (x:xs) = f x (foldr f v xs) -- equation 2
As an example, consider foldr (*) 1 [3,2,4]:
foldr (*) 1 [3,2,4] =
3 * (foldr (*) 1 [2,4]) = (by equation 2 of foldr)
3 * (2 * (foldr (*) 1 [4])) = (by equation 2 of foldr)
3 * (2 * (4 * (foldr (*) 1 []))) = (by equation 2 of foldr)
3 * (2 * (4 * 1)) = (by equation 1 of foldr)
= 24
You can do so with a fold function:
foldr (*) 1 [2,3,4]
or...
foldr1 (*) [2,3,4]
The product function is exactly what you're looking for.
It has also the feature that product [] equals 1, as you would expect mathematically speaking.
If you look at its definition, you can see that product is indeed the fold of multiplication (with 1 as neutral element).

Exception: divide by zero [closed]

I wanted to find out the list with all powers of 2 that divide 10! it is showing exception i.e. divide by zero
[2^i | i<-[1..],(factorial(10) `mod` (2^i))==0]
the complete question was to get the function largest_Power such that
largest_Power :: Int -> Int -> Int
largest_Power n p
is the largest power of p that divides n! (factorial of n)
And i tried to make this
largest_Power :: Int->Int->Int
largest_Power 0 _ =1
largest_Power _ 0 =1
largest_Power n p = floor (logBase (fromIntegral p) (fromIntegral (last([p^i | i<-[1..],(factorial(n) `mod` (p^i))==0]))))
factorial::Int->Int
factorial 0=1
factorial 1=1
factorial x=x*factorial(x-1)
Now when i ran this for largestPower 10 2 .I am getting exception.
What went wrong with Int?
Well Int has a bounded range - on most systems -(2^63) to 2^63-1.
Now you start with 1 (which is 1 in binary too) and then add zeroes in binary (which is the same as multiplying by 2) - you always only have one 1 followed by 0s. At some point you hid the representation of the lower-bound (the highest bit will represent a marker for positive or negative values) and then you will add yet another 0 which will overflow the Int end end you with only 0s.
You can check this easily:
Prelude> take 64 $ [2^i | i <- [1..]] :: [Int]
[2,4,8,16,32,64,128,
...
,4611686018427387904,-9223372036854775808,0]
That's where the division by zero in your original answer came from.
Why is you list comprehension ending up in bottom
The next problem you have is, that at one point the list-comprehension
[2^i | i<-[1..],(factorial(10) `mod` (2^i))==0]
will hang and not produce any more values.
The reason is simple: for big enough i: 2^i > factorial(10) and will never again divide it.
That's why I would recommend pulling out the filter for the mod and first bounding the list to a this hard-limit:
I don't want to write factorial 10 over and over again so I first define
let m = product [1..10] which is the definition of factorial 10
[2^i | i <- [1..]] is a list of all numbers in the form 2^i
only those smaller m are interesting so let's take only those: takeWhile (<= m) [2^i | i <- [1..]]
now the list is finite and it's no problem to use filter: filter (\n -> m `mod` n == 0) $ takeWhile (<= m) [5^i | i <- [1..]]
which yields:
λ> let m = product [1..10]
in filter (\n -> m `mod` n == 0)
$ takeWhile (<= m)
[2^i | i <- [1..]]
[2,4,8,16,32,64,128,256]
solving your problem
of course it turns out that your problem was given as:
the question was to define a function largest_Power such that
largest_Power :: Int -> Int -> Int with largest_Power n p is the largest
power of p that divides factorial n
I assume for now that you have to deal with the Ints there so you have to springle in some fromIntegral to deal with the conversions.
A solution based on your idea and the above snippet could be:
largest_Power :: Int -> Int -> Int
largest_Power n p = fromIntegral . last $ factorList n p
factorList :: Int -> Int -> [Integer]
factorList n p =
filter (\n -> m `mod` n == 0)
$ takeWhile (<= m) [p'^i | i <- [1..]]
where m = fromIntegral $ factorial n
p' = fromIntegral p
factorial :: Int -> Integer
factorial n = product [1..fromIntegral n]
if you indeed are only interested in the i from p^i then you can just push this into a tuple and adapt the algorithm a bit:
factorList :: Int -> Int -> [Integer]
factorList n p =
map fst
. filter (\(_,n) -> m `mod` n == 0)
$ takeWhile ((<= m) . snd) [(i,p'^i) | i <- [1..]]
where m = fromIntegral $ factorial n
p' = fromIntegral p
the rest of the program can stay unchanged
rethinking the algorithm
now if you think about what's going on it honestly doesn't seem to make sense to first create a huge number factorial n and then test for divisibility when all we need is the number or times we can divide this number by another (without rest) and when we know that this huge number is just a factor of really small numbers - because the we just can check the smaller numbers and then add up.
So if you are only interested in the i from p^i again than this will do as well:
factorCount :: Integral a => a -> a -> a
factorCount n p =
let (n',r) = n `divMod` p
in if r == 0 then 1 + factorCount n' p else 0
largest_Power :: Integral a => a -> a -> a
largest_Power n p = sum [ factorCount i p | i <- [1..n] ]
but should be a lot faster for bigger numbers.
Note that you can get this faster still if you memoize the factorCount which you probably should if this is an problem for an online contest .. which I suspect ^^

Haskell - Defining result as a list and returning null

listX n = xs
if sum[x | x <- [2, 4..n-1], y <- [1..n-1], y `rem` x == 0] == y
then insert y xs
else return ()
Alright, first time trying to work with Haskell, and only having novice Java knowledge has led to some problems.
What I was trying to do, was to define the result of the function listX n as a list called xs.
My idea was that the program would grab every number of from 1 to n, and check if it was equal to the sum of its positive divisors.
Clearly, I have failed horribly and need help, pointers to concepts I haven't understood is extremely appreciated.
Your main problem seems to be that you still think imperative (with the insert) - also () is the value unit - you probably wanted to write [] (the empty list) instead - but still the xs here is totally undefined so you would have to fix this too (and I don't see how to be honest).
perfect numbers
I think I can see a basic idea in there, and I think the best way to fix this is to go full list-comprehension (as you seem to understand them quite well) - here is a version that should work:
listX n = [ x | x <- [1..n], sum [ y | y <- [1..x-1], x `mod` y == 0] == x]
As you can see I changed this a bit - first I check all x from 1 to n if they could be perfect - and I do this by checking by summing up all proper divisors and checking if the sum is equal to x (that's the job of the sum [...] == x part) - in case you don't know this works because you can add guards to list comprehensions (the sum [..] == x filters out all values of x where this is true).
a nicer version
to make this a bit more readable (and separate the concerns) I would suggest writing it that way:
properDivisors :: Integer -> [Integer]
properDivisors n = [ d | d <- [1..n-1], n `mod` d == 0]
isPerfect :: Integer -> Bool
isPerfect n = sum (properDivisors n) == n
perfectNumbers :: [Integer]
perfectNumbers = filter isPerfect [1..]
perfectNumbersUpTo :: Integer -> [Integer]
perfectNumbersUpTo n = takeWhile (<= n) perfectNumbers

Haskell- Find element in a list and return its position

So i need to make a function described as
invFib :: Integer -> Maybe Integer
which takes an Integer and looks for it in the fibonacci sequence (as described by the function below)
fibs :: [Integer]
fibs = 0:1:(zipWith (+) fibs (tail fibs))
and returns the index of the number example:
invFib 0 ~> Just 0
invFib 1 ~> Just 1 or Just 2
map invFib [54, 55, 56] ~> [Nothing,Just 10,Nothing]
invFib (fibs !! 99) ~> Just 99
I tried making a function that takes a list of integers and spits out the index, but it keeps failing. Any thoughts?
this is function i tried-
findNum :: [Integer] -> Integer -> Integer -> Integer
findNum x:xs y z = if x == y
then z
else findNum xs y (z+1)
Edit:
the function freezes on numbers not in the fibonacci sequence, also only shows 1 value when 1 is entered
invFib :: Integer -> Maybe Integer
invFib n = if n < 0
then Nothing
else fmap fromIntegral (elemIndex n fibs)
So the key here is that fibs is infinite, but also monotonically increasing. Hence, once it exceeds the number being looked for, it can return Nothing:
findIndexInAscendingList :: (Ord a) => a -> [a] -> Maybe Integer
findIndexInAscendingList a xs = find 0 xs
where
find i [] = Nothing -- won't get used for fibs
find i (x:xs) | a == x = Just i
| a < x = Nothing
| otherwise = find (i + 1) xs
invFib :: Integer -> Maybe Integer
invFib n = findIndexInAscendingList n fibs
And so:
$ ghci
GHCi, version 7.4.2: http://www.haskell.org/ghc/ :? for help
λ: :load Fib.hs
[1 of 1] Compiling Main ( Fib.hs, interpreted )
Ok, modules loaded: Main.
λ: map invFib [54,55,56]
[Nothing,Just 10,Nothing]
There are some other ways to do it too. Think about zip fibs [0..] and then you could use dropWhile to remove the portion less than n and test what's left.
Why not use a function like 'takeWhile' to return a section of the infinite 'fibs' list that you want to examine? With the finite list, you could apply a function like 'elemIndex' which, with a little type adjustment, could return what you are after.
elemIndex myInteger (takeWhile (<= myInteger) fibs)
If you've already computed fibs, then the answer is simple:
import Data.List
invFib :: Integer -> Maybe Integer
invFib n = fmap fromIntegral (elemIndex n fibs)
fibs :: [Integer]
fibs = 0:1:(zipWith (+) fibs (tail fibs))

How to divide a pair of Num values?

Here is a function that takes a pair of Integral
values and divides them:
divide_v1 :: Integral a => (a, a) -> a
divide_v1 (m, n) = (m + n) `div` 2
I invoke the function with a pair of Integral
values and it works as expected:
divide_v1 (1, 3)
Great. That's perfect if my numbers are always Integrals.
Here is a function that takes a pair of Fractional
values and divides them:
divide_v2 :: Fractional a => (a, a) -> a
divide_v2 (m, n) = (m + n) / 2
I invoke the function with a pair of Fractional
values and it works as expected:
divide_v2 (1.0, 3.0)
Great. That's perfect if my numbers are always Fractionals.
I would like a function that works regardless of whether the
numbers are Integrals or Fractionals:
divide_v3 :: Num a => (a, a) -> a
divide_v3 (m, n) = (m + n) ___ 2
What operator do I use for _?
To expand on what AndrewC said, div doesn't have the same properties that / does. For example, in maths, if a divided by b = c, then c times b == a. When working with types like Double and Float, the operations / and * satisfy this property (to the extent that the accuracy of the type allows). But when using div with Ints, the property doesn't hold true. 5 div 3 = 1, but 1*3 /= 5! So if you want to use the same "divide operation" for a variety of numeric types, you need to think about how you want it to behave. Also, you almost certainly wouldn't want to use the same operator /, because that would be misleading.
If you want your "divide operation" to return the same type as its operands, here's one way to accomplish that:
class Divideable a where
mydiv :: a -> a -> a
instance Divideable Int where
mydiv = div
instance Divideable Double where
mydiv = (/)
In GHCi, it looks like this:
λ> 5 `mydiv` 3 :: Int
1
λ> 5 `mydiv` 3 :: Double
1.6666666666666667
λ> 5.0 `mydiv` 3.0 :: Double
1.6666666666666667
On the other hand, if you want to do "true" division, you would need to convert the integral types like this:
class Divideable2 a where
mydiv2 :: a -> a -> Double
instance Divideable2 Int where
mydiv2 a b = fromIntegral a / fromIntegral b
instance Divideable2 Double where
mydiv2 = (/)
In GHCi, this gives:
λ> 5 `mydiv2` 3
1.6666666666666667
λ> 5.0 `mydiv2` 3.0
1.6666666666666667
I think you are looking for Associated Types which allows for implicit type coercion and are explained quite nicely here. Below is an example for the addition of doubles and integers.
class Add a b where
type SumTy a b
add :: a -> b -> SumTy a b
instance Add Integer Double where
type SumTy Integer Double = Double
add x y = fromIntegral x + y
instance Add Double Integer where
type SumTy Double Integer = Double
add x y = x + fromIntegral y
instance (Num a) => Add a a where
type SumTy a a = a
add x y = x + y

Resources