You can get the head and the tail by pattern matching. Lets say you have a function that takes a list: myfunction list = -- do something here go = myfuction [1,4,2,6] ... you can write the "list" bit of the function as (x:xs), where x is the head, or first element, of the list, and xs is the tail, or the rest of the list: myfunction (x:xs) = -- do something here then you can call myfunction on xs, and compare that to x, to give the result. This is recursive: the function calls itself over and over again, until at some point it's going to execute "myfuction []" or "myfunction [6]", which is easy to handle, for example by adding the definition: myfunction [a] = -- the value of myfunction given a Go here for a really great tutorial: http://www.cs.nott.ac.uk/~gmh/book.html Recursive functions are in slides, number 6, but the tutorials are really great: just start from 1 and work your way through.

On 19/07/07, Steve Schafer wrote:

On Thu, 19 Jul 2007 10:55:19 -0700 (PDT), you wrote:

...

The question suggests to use some functions defined in the section, and one of them is iSort.

Aha. Well, that one certainly lends itself better to this particular proplen than either map or filter.

...

minimumValue :: [Int] -> Int minimumValue ns = head (iSort ns)

If I were going to use a sort, then yes, that's the way I would do it. Of course, sorting isn't the best way to solve the problem, as sorting will always be at least O(n * log n), whereas a more straightforward algorithm would be O(n).

Actually, since Haskell is lazy and only the first element is required for minimumValue, the above algorithm should be O(n). -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862

On 19/07/07, Aaron Denney wrote:

On 2007-07-19, Sebastian Sylvan wrote:

...

On 19/07/07, Steve Schafer wrote:

...

On Thu, 19 Jul 2007 10:55:19 -0700 (PDT), you wrote:

...

The question suggests to use some functions defined in the section, and one of them is iSort.

Aha. Well, that one certainly lends itself better to this particular proplen than either map or filter.

...

minimumValue :: [Int] -> Int minimumValue ns = head (iSort ns)

If I were going to use a sort, then yes, that's the way I would do it. Of course, sorting isn't the best way to solve the problem, as sorting will always be at least O(n * log n), whereas a more straightforward algorithm would be O(n).

Actually, since Haskell is lazy and only the first element is required for minimumValue, the above algorithm should be O(n).

I'm pretty sure that it's possible for to get O(n) behaviour, but that it's not guaranteed. It really should depends on the sort supplied.

Well iSort is the typical name one gives to insertion sort, so I assumed that was what the algorithm he was referring to. -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862

On 7/19/07, Sebastian Sylvan wrote:

Actually, since Haskell is lazy and only the first element is required for minimumValue, the above algorithm should be O(n).

That's pretty cool :-)

I have defined the first line it seems right to me but second line not sure. I have True or False and whatever value i give it produces that value. allEqual :: [Int] -> Bool allEqual (x1:x2:xs) = (x1 == x2) && allEqual xs allEqual _ = ??? Steve Schafer wrote:

On Thu, 19 Jul 2007 10:55:19 -0700 (PDT), you wrote:

...

The question suggests to use some functions defined in the section, and

one

...

of them is iSort.

Aha. Well, that one certainly lends itself better to this particular proplen than either map or filter.

...

minimumValue :: [Int] -> Int minimumValue ns = head (iSort ns)

If I were going to use a sort, then yes, that's the way I would do it. Of course, sorting isn't the best way to solve the problem, as sorting will always be at least O(n * log n), whereas a more straightforward algorithm would be O(n).

...

The other question is to test whether the values of allEqual on inputs 0 to n are all equal. Again, I defined the method but not sure if its concise?

allEqual :: [Int] -> Bool allEqual xs = length xs == length (filter isEqual xs) where isEqual n = (head xs) == n

Simple recursion is probably the most conceptually straightforward approach here. One little difficulty with this problem (and with minimumValue, too) is that the problem isn't completely specified, because we don't know what answer we're supposed to give when the list is empty. Let's assume that allEqual is supposed to return True on an empty list. In that case, we can write it like this:

allEqual :: [Int] -> Bool allEqual (x1:x2:xs) = ??? allEqual _ = ???

where the two ???s are left as an exercise for the reader.

-Steve _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- View this message in context: http://www.nabble.com/Producing-MinimumValue-tf4106379.html#a11696192 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

The standard (and simplest) definition for universally quantified predicates (all) starts with True and looks for a False occurrance: Prelude> all even [] True Conversely, existentially-quantified predicates (any) start with False and looks for a True occurrance: Prelude> any even [] False I would define: allEqual [] = True allEqual [_] = True allEqual (x1:x2:xs) = (x1 == x2) && allEqual xs As a purely stylistic note, (per a previous mail thread) you don't need to worry about the order that mutually-exclusive patterns are listed, so I find it clearer to put the base case of an induction first, so I don't forget it. Dan Alexteslin wrote:

I have defined the first line it seems right to me but second line not sure. I have True or False and whatever value i give it produces that value.

allEqual :: [Int] -> Bool allEqual (x1:x2:xs) = (x1 == x2) && allEqual xs allEqual _ = ???

Steve Schafer wrote:

...

On Thu, 19 Jul 2007 10:55:19 -0700 (PDT), you wrote:

...

The question suggests to use some functions defined in the section, and one of them is iSort. Aha. Well, that one certainly lends itself better to this particular proplen than either map or filter.

...

minimumValue :: [Int] -> Int minimumValue ns = head (iSort ns) If I were going to use a sort, then yes, that's the way I would do it. Of course, sorting isn't the best way to solve the problem, as sorting will always be at least O(n * log n), whereas a more straightforward algorithm would be O(n).

...

The other question is to test whether the values of allEqual on inputs 0 to n are all equal. Again, I defined the method but not sure if its concise?

allEqual :: [Int] -> Bool allEqual xs = length xs == length (filter isEqual xs) where isEqual n = (head xs) == n Simple recursion is probably the most conceptually straightforward approach here. One little difficulty with this problem (and with minimumValue, too) is that the problem isn't completely specified, because we don't know what answer we're supposed to give when the list is empty. Let's assume that allEqual is supposed to return True on an empty list. In that case, we can write it like this:

allEqual :: [Int] -> Bool allEqual (x1:x2:xs) = ??? allEqual _ = ???

where the two ???s are left as an exercise for the reader.

-Steve _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Oops, you got me. I didn't even look at the third line, I just took it from the previous post. My first instinct actually was to write: allEqual x@(h:t) = and (zipWith (==) x t) but I don't think that zipWith is allowed in the question. Dan Antoine Latter wrote:

On 7/19/07, Dan Weston wrote:

...

I would define:

allEqual [] = True allEqual [_] = True allEqual (x1:x2:xs) = (x1 == x2) && allEqual xs

What does this function do for "allEqual [1, 1, 2]" ?

Antoine _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On 7/19/07, Jason Dagit wrote:

On 7/19/07, Dan Weston wrote:

...

Oops, you got me. I didn't even look at the third line, I just took it from the previous post. My first instinct actually was to write:

allEqual x@(h:t) = and (zipWith (==) x t)

I prefer,

allEqual [] = True allEqual xs = foldl1 (==) xs

But, unfortunately, it's not a one liner like yours (unless you allow allEqual [] = undefined).

Oh and silly me, that only works for [Bool]. I'll hushup :) Jason

...

but I don't think that zipWith is allowed in the question.

Dan

Antoine Latter wrote:

...

On 7/19/07, Dan Weston wrote:

...

I would define:

allEqual [] = True allEqual [_] = True allEqual (x1:x2:xs) = (x1 == x2) && allEqual xs

What does this function do for "allEqual [1, 1, 2]" ?

Antoine _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

What wrong with my original solution? allEqual2 :: [Int] -> Bool allEqual2 xs = length xs == length (filter isEqual xs) where isEqual n = (head xs) == n It looks simpler to me Dan Weston wrote:

The real lesson here is that

1) no problem is "too easy" to cheat good software engineering practices. 2) no solution not accompanied by at least a QuickCheck result should be viewed with suspicion

I obviously have to go back and relearn these lessons.

Dan

Jason Dagit wrote:

...

On 7/19/07, Jason Dagit wrote:

...

On 7/19/07, Dan Weston wrote:

...

Oops, you got me. I didn't even look at the third line, I just took it from the previous post. My first instinct actually was to write:

allEqual x@(h:t) = and (zipWith (==) x t)

I prefer,

allEqual [] = True allEqual xs = foldl1 (==) xs

But, unfortunately, it's not a one liner like yours (unless you allow allEqual [] = undefined).

Oh and silly me, that only works for [Bool].

I'll hushup :)

Jason

...

...

but I don't think that zipWith is allowed in the question.

Dan

Antoine Latter wrote:

...

On 7/19/07, Dan Weston wrote:

...

I would define:

allEqual [] = True allEqual [_] = True allEqual (x1:x2:xs) = (x1 == x2) && allEqual xs

What does this function do for "allEqual [1, 1, 2]" ?

Antoine _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- View this message in context: http://www.nabble.com/Producing-MinimumValue-tf4106379.html#a11697071 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

On 7/19/07, Alexteslin wrote:

What wrong with my original solution?

allEqual2 :: [Int] -> Bool allEqual2 xs = length xs == length (filter isEqual xs) where isEqual n = (head xs) == n

It looks simpler to me

I believe it's correct, but the use of "length" and "filter" seems forced. For example, for a very long list that has the second element mismatch, the versions with explicit recursion (or fold variants) will terminate with False as soon as a mismatch is found; the "length" version will not terminate until both have been fully traversed. If you're allowed to use everything, perhaps the clearest would be: allEqual3 [] = True allEqual3 (x:xs) = all (== x) xs (with "all" built on top of a fold.) Colin

Hello Benja, Friday, July 20, 2007, 6:10:15 PM, you wrote:

My natural instinct is,

allEqual [] = True allEqual (x:xs) = all (== x) xs

with the same caveat about allEqual [] as in your case.

allEqual xs = all (== head xs) xs -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Thanks you, that works fine. Sometimes I am not sure what the exercise asks. For example in the section of higher order functions i presume most exercises would be to use those functions, but it seems that that not always true. Dan Weston wrote:

The standard (and simplest) definition for universally quantified predicates (all) starts with True and looks for a False occurrance:

Prelude> all even [] True

Conversely, existentially-quantified predicates (any) start with False and looks for a True occurrance:

Prelude> any even [] False

I would define:

allEqual [] = True allEqual [_] = True allEqual (x1:x2:xs) = (x1 == x2) && allEqual xs

As a purely stylistic note, (per a previous mail thread) you don't need to worry about the order that mutually-exclusive patterns are listed, so I find it clearer to put the base case of an induction first, so I don't forget it.

Dan

Alexteslin wrote:

...

I have defined the first line it seems right to me but second line not sure. I have True or False and whatever value i give it produces that value.

allEqual :: [Int] -> Bool allEqual (x1:x2:xs) = (x1 == x2) && allEqual xs allEqual _ = ???

Steve Schafer wrote:

...

On Thu, 19 Jul 2007 10:55:19 -0700 (PDT), you wrote:

...

The question suggests to use some functions defined in the section, and one of them is iSort. Aha. Well, that one certainly lends itself better to this particular proplen than either map or filter.

...

minimumValue :: [Int] -> Int minimumValue ns = head (iSort ns) If I were going to use a sort, then yes, that's the way I would do it. Of course, sorting isn't the best way to solve the problem, as sorting will always be at least O(n * log n), whereas a more straightforward algorithm would be O(n).

...

The other question is to test whether the values of allEqual on inputs 0 to n are all equal. Again, I defined the method but not sure if its concise?

allEqual :: [Int] -> Bool allEqual xs = length xs == length (filter isEqual xs) where isEqual n = (head xs) == n Simple recursion is probably the most conceptually straightforward approach here. One little difficulty with this problem (and with minimumValue, too) is that the problem isn't completely specified, because we don't know what answer we're supposed to give when the list is empty. Let's assume that allEqual is supposed to return True on an empty list. In that case, we can write it like this:

allEqual :: [Int] -> Bool allEqual (x1:x2:xs) = ??? allEqual _ = ???

where the two ???s are left as an exercise for the reader.

-Steve _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- View this message in context: http://www.nabble.com/Producing-MinimumValue-tf4106379.html#a11696723 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.