2

I have the following question:

Define the functions

and, or :: [Bool] -> Bool

which give the conjunction and disjunction of a list of Booleans. For instance,

and [False, True] = False
or  [False, True] = True

On an empty list and gives True and or gives False; explain the reason for these choices.

I know I can answer it but am not sure of the most efficient way to lay it out. Any help would be much appreciated.

My solution was this (but I think it could be more efficient):

and, or :: [Bool] -> Bool

and []             = True
and [True, True]   = True
and [False, False] = True
and [True, False]  = False

or []             = False
or [True, True]   = False
or [False, False] = False
or [True, False]  = True
Improve this question
2
  • Yes, it's homework @Don Stewart and I've now tagged it as such :) I know how to do the function, and this is what I've done (I believe there is a more efficient way to do it though - it's outlined above now). Commented May 9, 2011 at 5:06
  • It's not Haskell, but you may be interested in How To Design Programs, which does an excellent job of stepping you through, well, how to design programs (much like the two answers thus far have done). Commented May 9, 2011 at 23:32

4 Answers 4

Reset to default
8

The key step you're going to have to make is to think inductively. Your current solution:

and :: [Bool] -> Bool

and []             = True
and [True, True]   = True
and [False, False] = True
and [True, False]  = False

enumerates some of the possibilities, but it obviously doesn't work for all lists. So how to write one that will work for lists of any length?

In Haskell, you can usually write your functions by taking apart a data type. In this case, lists. Lists are defined as:

data [a] = []
         | a : [a]

So, lists have two cases: either the empty list, or a one element with a tail. Let's start writing your and function then, so that it matches those two cases for lists:

and []     = True
and (a:as) = ...

So, the "base case", the empty list, is True. But what should we do for the case of a list with one element, and some tail?

Well, we already have the && function in Haskell:

> True && True
True
> True && False
False
> False && True
False
> False && False
False

Interesting! So, && takes two arguments, and correctly determines if both arguments are True. And we are currently have a list with one element, and a list for a tail. And at the same time, we're defining the and function, that results in a single boolean value when applied to a list.

So we can make the inductive step and use the function we're defining, and, together with the && binary operator, to finish our definition:

and []     = True
and (a:as) = a && (and as)

So we evaluate the tail of the list to some value (recursively), and use the && operator to combined that value with the current value, and that's our function written.

Recursion and induction, driven by the recursive structure of the lists, are the key technique to learn in programming. If you can write this, you're making a big step forward.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Uh, unless I've missed something, the question is asking him to explain the choices for and [] and or [], not how to implement those functions.
They also wanted defined it in the form and, or :: [Bool] -> Bool
@luqui -- re-reading: the question looks clearly to me to be asking how to write and and or, given some example behavior, and the OP is stuck on recursion, no?
In terms of pedagogy, is it more useful to start with recursion or to use HoF like foldl? I learned recursion first, but I'm starting to think that the other way may have been better. (Here it seems like Maclunian is studying recursive defs so it's academic, but still...)
@John L: Well, you only really learn to love folds after you have done some recursion by hand, right?
8

I would suggest to use pattern matching to dissect the list. Start with these condidtions:

and [] = True
and (True : xs) = ...
and (False : xs) = ...

OK, for an empty list and is True. If a list starts with a "True" head, how do you determinde the "truth" of the complete list? Do you need a recursive call or not? What if you have a "False" head?

The or case is similar, just start with or [] = False

Note that when you start with these definitions, which already pattern match on the truth values, you don't even need to use && or ||.

Improve this answer

2 Comments

Upvoting because I appreciate this style of answer to homework questions.
Me too. (I know, that such comments are not liked on SO)
1

Here are few bits from me:

and [] = True
and (True : xs) = and xs
and (False : xs) = False

or [] = False
or (True : xs) = True
or (False : xs) = or xs

Sorry, if I have spoiled the "homework" mode of this question.

Improve this answer

2 Comments

Yes, you did. You just completed the starting point I gave. Why?
I don't know.. I did it when I was unconscious :)
0

i tried to solve this with folds

and = foldl (&&) True
or = foldl (||) False

this would be a simple solution to write - but i think a more abstract one and takes a [Bool] and &&s the first element of this list with the accumulator True this result will be the next accumulator to foldl with.

yours ε/2

Improve this answer

1 Comment

It's probably better to use foldr. That way you get short circuiting for free and can avoid evaluating the whole spine of the list. Try foldl (&&) True (False : undefined) with foldr to see the difference.

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.