4

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
5
  • First off I'd recommend reading a proper tutorial on haskell, like Learn You A Haskell, it's free! More to the point, error doesn't work the way you're trying to use it. It should generally be avoided, you're better of looking into Maybe. Commented May 1, 2013 at 9:37
  • I've been reading Learn You A Haskell, I couldnt quite find an answer to my problem there tho but I probably just didnt go far enough! Thanks anwyways, I will look into the Maybe Commented May 1, 2013 at 9:57
  • Can you write it in a imperative language? Its probably easier to understand if you could compare it. Post it on jsfiddle.net and will try to translate it in haskell. Commented May 1, 2013 at 10:10
  • I can't. Haskell is the first language im learning. Commented May 1, 2013 at 10:13
  • ok post your complete code on hpaste.org so we have a better picture. Also I recommend hanging around in haskell irc for a while to ask small direct questions while you are trying stuff out. Commented May 1, 2013 at 10:19

5 Answers 5

6

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
Sign up to request clarification or add additional context in comments.

4 Comments

Thanks! This works very well, I will try to recreate it myself now.
Ahh, I'm a happy puppey right now! I was able to recreate your function and I managed to create the check function following your example. I think this really helped me understand recursion! Thanks a lot. Sadly it seems like I can't copy my checkfunction into the comments withotu it looking awful :D
@user2299050: You could write up your solution as an answer as well!
@yatima2975 hah, yeah, I guess Im gonna do that! :D
6

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'

3 Comments

your foldrMyPile is a left fold (with flipped combining function, f), not a right fold. :) for one thing, it is tail-recursive. as such, there's no early cut-off in your elemPile.
You're right! Though actually, I suppose it depends on what you call left and right... Anyway, changed the name and signature.
no, there is a marked difference. left fold is tail-recursive and can't stop early. right fold is guarded recursive and can. (go n z | highestNumber n = f n z | otherwise = f n $ go (above n) z).
3

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.

Comments

2

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.

4 Comments

on the contrary, it doesn't exist. :) Hoogle knows nothing about it.
@Will this is funny. Frege has this, so I thought Haskell has it, too. Same with dropWhile and dropUntil, it seems.
:) does your takeUntil include the breaking element?
It should, shouldn't it, otherwise it could always be written as takeWhile (not . p). Quick check turns out it doesn't, though (grrrr). Anyway, the more thanks go to you for clarifying.
2

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.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.