viernes, 25 de abril de 2014

Estructura Bag (saco) en Haskell. Estructuras de Datos

Buenas gente. Iba a escribir sobre una práctica de Java, pero he visto que los conceptos no venían explicados en los apuntes, por lo que primero haremos la parte de Haskell que es donde mejor lo explican. Aquí teneis el enunciado:

Un saco (o multiconjunto) es parecido a un conjunto salvo que un elemento puede estar incluido varias veces. Por ejemplo, {‘b’, ‘a’, ‘d’, ‘d’, ‘a’, ‘c’ , b’, ‘a’} es un saco que incluye tres ocurrencias del carácter ‘a’ , dos ocurrencias del ‘b’, una del ‘c’ y dos del ‘d’.

a) Implementa sacos en Haskell usando el siguiente tipo de datos:
data Bag a = Empty | Node a Int (Bag a)
De forma que en cada nodo aparece, además del saco restante, cada elemento junto con su contador de ocurrencias, o sea, el número de veces que aparece. Para agilizar las operaciones de inserción y borrado en un Bag, interesa que los nodos estén ordenados atendiendo al orden de los elementos a incluir. Además, no deben aparecer elementos con contador nulo (o negativo). Por ejemplo, el saco anterior se representa por:
Node ‘a’ 3 (Node ‘b’ 2 (Node ‘c’ 1 (Node ‘d’ 2 Empty)))
La implementación debe incluir las siguientes funciones:
empty :: Bag a -- Devuelve un saco vacío
isEmpty :: Bag a -> Bool -- Comprueba si un saco está vacío
insert :: (Ord a) => a -> Bag a -> Bag a --Inserta una nueva ocurrencia
occurrences :: (Ord a) => a -> Bag a -> Int -- Devuelve el número de -- ocurrencias de un elemento en un saco (0 si el elemento no está) -}
delete :: (Ord a) => a -> Bag a -> Bag a -- Borra una ocurrencia de un -- elemento de un saco. Devuelve el mismo saco si el elemento no estaba incluido

b) Proporciona una especificación de Bag definiendo sus axiomas para las diferentes operaciones y comprueba la implementación realizada con QuickCheck. Para ello, incluye en el módulo la siguiente instancia para generar sacos aleatorios:
instance (Ord a, Arbitrary a) => Arbitrary (Bag a) where
arbitrary = do
xs <- listOf arbitrary
return (foldr insert empty xs) 

La solución es la siguiente:

module DataStructures.Bag.LinearBag
  ( Bag
  , empty
  , isEmpty
  , insert
  , delete
  , occurrences
  ) where

import Data.List(intercalate)
import Test.QuickCheck

data Bag a = Empty | Node a Int (Bag a)

empty :: Bag a
empty = Empty

isEmpty :: Bag a -> Bool
isEmpty Empty = True
isEmpty _     = False

insert :: (Ord a) => a -> Bag a -> Bag a
insert x Empty = Node x 1 Empty
insert x (Node y n b)
  | x<y        = Node x 1 (Node y n b)
  | x==y       = Node y (n+1) b
  | otherwise  = Node y n (insert x b)

occurrences :: (Ord a) => a -> Bag a -> Int
occurrences x Empty = 0
occurrences x (Node y n b)
  | x<y             = 0
  | x==y            = n
  | otherwise       = occurrences x b

delete :: (Ord a) => a -> Bag a -> Bag a
delete x Empty = Empty
delete x (Node y n b)
  | x<y        = Node y n b
  | x==y       = if n>1 then Node y (n-1) b else b
  | otherwise  = delete x b

-- Showing a bag
instance (Show a) => Show (Bag a) where
        show b = "LinearBag(" ++ intercalate "," (map show (elems b)) ++")"
          where
            elems Empty        = []
            elems (Node x n b) = replicate n x ++ elems b

-- bag equality
instance (Eq a) => Eq (Bag a) where
  Empty        == Empty            = True
  (Node x n b) == (Node x' n' b')  = x==x' && n==n' && b==b'
  _            == _                = False

-- This instace is used by QuickCheck to generate random bags
instance (Ord a, Arbitrary a) => Arbitrary (Bag a) where
    arbitrary = do
      xs <- listOf arbitrary
      return (foldr insert empty xs)
 


He de decir que ésta solución no está mal, pues ha sido implementada por un profesor y es la que se utilizaba de prueba para los que no sabían hacerla y la necesitaban. Yo si supe hacerla, pero como quiero que tengáis el material de mejor calidad posible, agradecedle a Pepe Gallardo (el mejor en Haskell que conozco) el código.

Saludos, el domingo subo el homónimo en Java ;)

No hay comentarios:

Publicar un comentario