Re: [Haskell-cafe] FOL
On Tue, 05 Jun 2007, at 00:41, Tony Morris wrote:
I would like to know if all 16 possible functions that accept two
boolean arguments have names in First-Order Logic. I know they have
Haskell function names (e.g. \p -> \_ -> id p, \_ -> \_ -> const
True),
but I'm hoping there is a more general name that is recognised by
anyone
with a feel for logic, but not necessarily Haskell.
I have listed all sixteen of these functions below using Haskell
(named
a to p) along with the name of those that I am aware of having a
name as
a comment.
Thanks for any tips.
{-
p q | a b c d e f g h i j k l m n o p
0 0 | 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 | 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 | 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 | 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
-}
Common Lisp has names for them. See:
http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/
node131.html#SECTION00167
and then search for
(boole boole-and x y) == (logand x y)
and look at the table just before that.
---Frank
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Problem with Infinite Lists
This is a bit off topic, but... Warning: contains evangelism from a number theorist. The Fibonacci sequence should start with 0 and 1 rather than 1 and 1. Doing so makes it adhere to the following property: all_fib !! (gcd m n) == gcd (all_fib !! m) (all_fib !! n) for m, n nonnegative integers. With the exception that Haskell misdefines gcd 0 0 as an error rather than 0. ---Frank On Wednesday, Sep 3, 2003, at 04:30 US/Eastern, Wamberto Vasconcelos wrote: Folks I am new in this forum, so apologies if this has been asked before. If this is the case, please point me to the direction of the answer and I won't bother you again! Also, could you make sure you CC your answers to me? I am not sure how long it takes for my subscription to be activated and I don't want to miss out on the action :-) The Problem I have defined this function to calculate the Fibonacci numbers: all_fib :: [Float] all_fib = 1:(1:(add_fib all_fib)) where add_fib (x:y:rs) = (x + y):(add_fib (y:rs)) Which seems to work: Main> take 20 all_fib [1.0,1.0,2.0,3.0,5.0,8.0,13.0,21.0,34.0,55.0,89.0,144.0,233.0,377.0, 610.0,987.0,1597.0,2584.0,4181.0,6765.0] However, when I tried Main> filter even (take 20 all_fib) ERROR - Illegal Haskell 98 class constraint in inferred type *** Expression : filter even (take 20 all_fib) *** Type : Integral Float => [Float] What is going on here? Thanks in advance for any help/hint. -- Wamberto Vasconcelos, PhD [EMAIL PROTECTED] Department of Computing Sciencehttp://www.csd.abdn.ac.uk/~wvasconc University of Aberdeen, Aberdeen AB24 3UE, Scotland, UK Phone +44 (0)1224 272283 Fax +44 (0)1224 273422 ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Homework
- I leave this morning for ICFP. - My laptop is broken, so I can't work on code for this on the plane. - The delights of Sweden will go less noticed, since the number theorist in me will not let me forget. (It's already saying, "It's such a simple description, how hard can it be? Just give it some thought.") This was cruel timing. ;-) ---Frank On Friday, Aug 22, 2003, at 02:25 US/Eastern, Andrew J Bromage wrote: G'day all. On Fri, Aug 22, 2003 at 03:41:14PM +1000, [EMAIL PROTECTED] wrote: Seeing as its thst time of year again and everyone is posting their homework, has anyone got any good puzzles to do? I wouldn't mind having a go at something a bit tricky. OK, here's a tricky problem. Take a list S. Delete some elements from the list. What you have left is a subsequence of S. For example, [1,3,2] is a subsequence of [2,1,2,1,3,2,1,3]. Consider the following list: [1,2,3,1,2,3,1] This list contains all permutations of the list [1,2,3] as subsequences. It is also minimal, in the sense that there is no shorter subsequence which will do (though there are potentially many minimal subsequences). We will call such a list a shortest supersequence over the alphabet [1..3]. The challenge is multi-part. You may answer as many or as few questions as you want. 1. Write a function sss :: Int -> [Int] where sss n is a shortest supersequence over the alphabet [1..n]. Make this as efficient as possible. Prove an upper-bound complexity on your function. 2. Write a function sss_length :: Int -> Int where sss_length n is the length of a shortest supersequence over the alphabet [1..n]. Make this as efficient as possible. Prove an upper-bound complexity on your function. If you can't solve this problem efficiently, write a function sss_length_bounds :: Int -> (Int,Int) which returns the best upper and lower bounds that you can. (Hint: n is a trivial lower bound, n^2 is a trivial upper bound. A tighter upper bound is n^2-n+1. Prove this as an exercise.) 3. Write a function sss_count :: Int -> Int where sss_count n is the number of shortest supersequences over the alphabet [1..n]. Make this as efficient as possible. Prove an upper-bound complexity on your function. (Hint: sss_count n must be a multiple of n factorial. Why?) If you can't solve this problem efficiently, write a function sss_count_bounds :: Int -> (Int,Int) which returns the best upper and lower bounds that you can. Incidentally, I don't have sub-exponential answers to any of these questions. You did ask for something "a bit tricky". Cheers, Andrew Bromage ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
