Implementing recursion in Haskell without input variable

Question

So im still very new to programming and I'm struggling a lot with the Syntax of Haskell. I kind of know what I want to implement but im not really sure how to do it so I came here to ask.

So what I have is a "pile" of Numbers in no particular order that are defined by 3 different functions. An example for this would be:

lowestnumber = 4
highestnumber 5 = True
highestnumber _ = False
above 4 = 11
above 11 = 18
above 18 = 2
above 2  = 3
above 3  = 5
above 5  = error "highest Number"
above _ = error "Not part of the pile"

Now for one I want to write a function that checks if a certain number is part of this pile and a different function "sum' = " that sums up all the elements of the list without an input variable. First I solved these problems by defining a list and using listcommands in order to sum up and see if something is "elem" of that list but I am supposed to solve it without using lists.

So I have ideas of how to solve this but I have no idea of how to actually write it without receiving countless errors. Some examples of what I've tried for the check function:

check x = if above x /= error "Not part of the stack" || lowestnumber == x then True else False

I also tried the checks with "_" like this but it wouldn't work either:

check x if above x == _ || lowestnumber == x then True else False

My idea for the sum function was this:

sum' = lowestnumber + above lowestnumber + above (above lowestnumber) + above (above (above lowestnumber))

or also something like

sum' = lowestnumber + (above sum') 

Which I understand woul

and so on but I did not figure out how I could implement this using recursion which is apparently the way to go.

Well hopefully this question isnt too stupid! I hope you can help me :)

Edit: Ok, so these are the solutions to my 3 function-problems

sumup' a b 
           |highestNumber a == True = a+b 
           |otherwise = sumup' (above a) (a+b)

sumup = sumup' lowestNumber 0



check' a b 
            |a == b = True
            |True == highestNumber a && a==b = True
            |True == highestNumber a && a/=b = False
            |check' (above a) (b) == True = True
            |otherwise = False

check b = check' (lowestNumber) (b)



above' :: Integer -> Integer -> Bool
above' x y
            | check x == False = False
            | check y == False = False
            | highestNumber y == True = False
            | highestNumber x == True = True
            | x==y = True
            | above' x (above y) == True = True
            | otherwise = False

Answer 1

About your three new functions.

sumup' a b 
       | highestNumber a == True = a+b 
       | otherwise = sumup' (above a) (a+b)

sumup = sumup' lowestNumber 0  -- sum up all numbers in the pile

this is almost exactly as in AndrewC'c answer. it is good, except == Temp is totally superfluous, not needed. sumup' also would usually be made an internal function, moved into a where clause. As such, it doesn't have to have a descriptive name. Some use (Scheme-inspired?) loop, some go (since do is a reserved syntax keyword). I personally started to use just g recently:

sumup = g lowestNumber 0     -- sum up all numbers in the pile
  where
    g n tot                  -- short, descriptive/suggestive var names 
       | highestNumber n  = n + tot    
       | otherwise        = g (above n) (n + tot)

---

check b = check' lowestNumber b   -- don't need any parens here

check' a b 
        |a == b = True
        |True == highestNumber a && a==b = True  -- `True ==` not needed
        |True == highestNumber a && a/=b = False -- `True ==` not needed
        |check' (above a) (b) == True = True     -- `== True` not needed
        |otherwise = False

This usually would be written as

check' a b = (a == b) ||
             (highestNumber a && a==b) || 
             (  not (highestNumber a && a/=b) 
                && check' (above a) b  )

in the 2nd test, if a==b were true, it'd already worked in the 1st rule, so we can assume that a/=b henceforth. so 2nd test is always false; and we get

check' a b = (a == b) ||
             (not (highestNumber a) && check' (above a) b)

which is rather OK looking. It can be also written with guards again, as

check' a b | (a == b)        = True
           | highestNumber a = False
           | otherwise       = check' (above a) b

or, using short suggestive variable names, and with swapped order of arguments, for consistency,

check' n i | highestNumber i = i == n 
           | otherwise       = i == n || check' n (above i)

which is rather similar to how the first, sumup code is structured.

---

Now, the third function. First of all, it can easily be defined in terms of check' too, just starting with the given low number instead of the lowest one:

higher top low = check low && not (highestNumber low) 
                           && check' top (above low) 

("higher" is a more distinctive name, yes?). Your version:

higher :: Integer -> Integer -> Bool
higher x y
        | check x == False = False         -- not(check x == False)  -- ==
        | check y == False = False         --     check x == True    -- ==
        | highestNumber y == True = False  --     check x
        | highestNumber x == True = True
        | x==y = True
        | higher x (above y) == True = True
        | otherwise = False

again, simplifying,

higher x y = check x && check y 
             && not (highestNumber y) 
             && ( highestNumber x 
                  || x==y                  -- really?
                  || higher x (above y) )  -- too strong

so this one seems buggy.

Answer 2

You're supposed to do this without lists, well that's sad because it would be very much the idiomatic solution.

The nextmost idiomatic one would be something generic that is able to traverse your pile there. You basically want a fold over the numbers:

foldlMyPile :: (a -> Int -> a) -> a -> {- Pile -> -} a
foldlMyPile f = go lowestNumber
 where go n accum
         | highestNumber n  = result
         | otherwise        = go (above n) result
        where result = f accum n

Once you've got this, you can use it to define sum, element etc. much like they are defined on lists:

sumPile :: Int
sumPile = foldlMyPile (+) 0

elemPile :: Int -> Bool
elemPile n = foldlMyPile $ \alreadyFound n' -> alreadyFound || n==n'

Answer 3

Various higher order functions in Haskell capture various recursion (and corecursion^†) patterns, like iterate, foldr, unfoldr, etc.

Here we can use until :: (a -> Bool) -> (a -> a) -> a -> a, where until p f x yields the result of iteratively applying f until p holds, starting with x:

sumPile = snd $ 
    until (highestnumber . fst) 
          (\(a,b)->(above a, b + above a)) 
          (lowestnumber,   lowestnumber)

also,

inThePile p = p==until (\n-> highestnumber n || n==p) above lowestnumber

---

^† basically, recursion with accumulator, building its result on the way forward from the starting case, whereas regular recursion builds its result on the way back from the base case.

Answer 4

First I solved these problems by defining a list and using listcommands in order to sum up and see if something is "elem" of that list but I am supposed to solve it without using lists.

You can solve this by expanding elem, like so:

x `elem` [1,2,3]

is the same as

x == 1 || x == 2 || x == 3

And while your at it

sum' = 4 + 11 + 18 + 2 + 4  + 5

You could also construct a list of all your elements with something like

elements = takeUntil highestnumber (iterate above lowestnumber)

takeUntil p xs = foldr (\x r -> if p x then [x] else x:r) [] xs

This is the only way I see you can write your check and sum' functions without using constants.

---

we can't use takeWhile (not . highestnumber) because we'll miss the highest number. So, takeUntil must be defined this way to include the breaking element in its output.

Answer 5

If you want to do this without lists, keep a running total, and use recursion.

If you're at the highestnumber, just add that to your current total and stop, otherwise, add the number to your total total + n and move on to the next one above n:

add n total |highestnumber n = total + n
            |otherwise = add (above n) (total + n)

Then you can do

answer = add lowestnumber 0