Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2012 / Funktionale Programmierung / Übungen / Übung 06 Teil 1


Inhaltsbereich

Übung 06 Teil 1

Funktionale Programmierung Übung 06 Teil 1 QuickCheck

Haskell source code icon 06Testing.hs — Haskell source code, 3 KB (3819 bytes)

Dateiinhalt

-- | Functional Programming, course at LMU, summer term 2012
--   Andreas Abel and Steffen Jost
--
-- Exercise sheet 6, 2012-06-12
--
-- Instructions:
--
-- Replace all occurrences of 'undefined' and 'Undefined' by sensible code.
-- Do not change the type of functions you are asked to implement!
-- Quickcheck test cases may help you finding bugs.
--
-- Spell out proofs where asked for.
--
-- Submit your solutions via UniWorX.

----------------------------------------------------------------------
-- Header
--
-- You can add imports and LANGUAGE pragmas here.
----------------------------------------------------------------------

{-# LANGUAGE TemplateHaskell #-}

module Monads where

import Control.Applicative

import Data.List

import Test.QuickCheck
import Test.QuickCheck.All

data Undefined

----------------------------------------------------------------------
-- Exercise 1  Context-free grammar
----------------------------------------------------------------------

{- Consider the following (ambiguous) context-free grammar.

     S -> (empty) | 'S' | "S" | SS

   It describes well-nested quotations, e.g. '', "", "''", '''', ...
   Bad words are "'"' or "'''"' and alike.

   a) First, write a push-down automaton that decides efficiently whether
      a word is a well-nested quotation, i.e., generated by the grammar.
-}

accept :: String -> Bool
accept s = undefined

{- b) Now write a generator for words of the grammar and make sure
      your automaton accepts all of them.
-}

quotGen :: Gen String
quotGen = undefined

prop_complete = forAll quotGen accept

{- c) Finally, make sure that your automaton only accepts words
      of the grammar.  To this end, we have provided an inefficient
      model solution accept0.

      Formulate and test a property that states that your solution
      does not accept more words than the model solution.
-}
accept0 :: String -> Bool
accept0 s =  all (`elem`  [ '\'', '\"' ]) s && iter s
  where iter [] = True
        iter s  = let s' = step s in length s' < length s && iter s'
        step s = concat $ filter (\g -> length g `mod` 2 == 1) $ group s

prop_sound = undefined

----------------------------------------------------------------------
-- Exercise 2
----------------------------------------------------------------------

{- Given a finite set A, there are only finitely many functions A -> A.
If the cardinality of A is n, then there are at most n^n functions A -> A.
For instance, there are only four different functions of type Bool -> Bool.
(Which are these?)

Consequently, if we iterate a function k-times, i.e., compute f^k x, there
might be a smaller number l such that f^k x = f^l x.

For instance, for A = Bool, given any f :: Bool -> Bool and any x :: Bool,

  f (f (f x)) == f x

i.e. the law holds for k=3 and l=1.
-}

prop_fff :: Fun Bool Bool -> Bool -> Bool
prop_fff (Fun _ f) x = iterate f x !! 3 == iterate f x !! 1

{- Use QuickCheck (or your brain, hehe!) to find a similar law
   for a type Tri of cardinality 3!
-}

type Tri = Undefined  -- that may also be a data or newtype

prop_fTri :: Fun Tri Tri -> Tri -> Bool
prop_fTri (Fun _ f) x = iterate f x !! k == iterate f x !! l
  where k = undefined
        l = undefined

----------------------------------------------------------------------
-- Exercise 3  See 06Agda.agda
----------------------------------------------------------------------

----------------------------------------------------------------------
-- Exercise 4  See 06Agda.agda
----------------------------------------------------------------------

----------------------------------------------------------------------
-- Haskell footer
----------------------------------------------------------------------

-- | Runs all tests starting with "prop_" in this file.
runTests = $quickCheckAll

Artikelaktionen


Funktionsleiste