how to implement Within function in Haskell?

Question

within :: (Ord a, Num a) => a -> [a] -> a

that takes a tolerance, that is, a number epsilon and an infinite list of numbers, and looks down the list to find two consecutive numbers in the list that differ by no more than epsilon it returns the second of these. (It might never return if there is no such pair of consecutive elements.) For example,

within 1.0 [1.0 ..] = 2.0
within 0.5 ([1.0, 32.5, 17.2346, 10.474, 8.29219, 8.00515]
++ [8.0, 8.0 ..])
= 8.00515

I actually don't know how to take 2 elements at a time and check if they differ by no more than epsilon. If I write something like check x y e = abs(x-y)<=e I don't really know how to use it in writing within function — Alice
– Alice, Commented Nov 9, 2015 at 22:55
I'm not at my PC, but I've written an answer about taking two elements of a list earlier today. It might be helpful. Basically use within eps (x:y:xs) = .... However, you should think about the function's behaviour if the list isn't infinite and/or doesn't contain a fitting pair. — Zeta
– Zeta, Commented Nov 9, 2015 at 22:59
Here is some inspiration: this function takes a list and returns a list of pairs of consecutive elements ap zip tail :: [a] -> [(a,a)] — cdk
– cdk, Commented Nov 9, 2015 at 23:02

user824425 · Accepted Answer · 2015-11-09 23:15:21Z

In Haskell, a list is just another data structure, perhaps with some (in my opinion) confusing notation. With any data structure, you can use pattern matching. When you're only working with lists, you have three possible things in a pattern:

A variable, like x.
A constructor applied to zero or more patterns,
- like with (:) x xs (or perhaps more familiarily: x:xs),
- or []

Note that, in patterns, you apply constructors to patterns. It's perfectly allowable to write (:) x ((:) y ys) (more commonly written as x:y:ys), which matches any list of at least two elements, and assigns the first element to x, the second to y, and the remainder of the list to ys.

The skeleton of your within function would look something like this:

theFunction theList = case theList of
                          x:y:ys -> if canGiveAnswer x y
                                        then buildAnswer x y
                                        else theFunction (y:ys)

Here, theFunction tries to match its input with the pattern x:y:ys, checks whether x and y are sufficient to give an answer, and do so when it can, or restart itself (theFunction (y:ys)) with the first element of the list removed.

You can write this more tersely like

theFunction (x:y:ys) = if canGiveAnswer x y then buildAnswer x y else theFunction (y:ys)

or even

theFunction (x:y:ys) | canGiveAnswer x y = buildAnswer x y
                     | True = theFunction (y:ys)

Of course, in your case, you need an extra argument:

within :: (Ord a, Num a) => a -> [a] -> a
within epsilon (x:y:ys) | canGiveAnswer x y epsilon = buildAnswer x y epsilon
                        | True = within epsilon (y:ys)

I'll leave it up to you to figure out what canGiveAnswer and buildAnswer are supposed to be.

Collectives™ on Stack Overflow

how to implement Within function in Haskell?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related