aplicación de principiante Catamorphism para los árboles no binarios en comparación con el patrón de diseño compuesto

Question

Por el momento, el sueño sigue adelante, en cada concepto Haskell me entero de que estoy más tentado. Sin embargo, yo no he cumplido por completo a trabajar en este precioso respuesta de @ Luqui a mi pregunta anterior sobre catamorphism , y voy a volver en ella hasta que está bien. Fue en este código de ejemplo en la Wikipedia, que trata de catamorphism en los árboles binarios de .

Sin embargo, he tratado de implementar catamorphism para NO BINARIO árboles pero enfrentarse a algunas dificultades:

data Composition a = Leaf a
                   | Composite [Composition a]

data CompositionAlgebra a r = CompositionAlgebra { leaf      :: a →  r
                                                 , composite :: [r] →  r }

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite [y]) =  map g [y] 

- que la última línea duerma favor GHC al "mapa g [y]"

maxOfPair :: a →  a →  a
maxOfPair x y = if( x > y) -- this doesnt please ghc either, Ordering trouble
                then (x) 
                else (y)

maxInList :: [a] →  a
maxInList (x:xs) = maxOfPair x (maxInList xs)

treeDepth :: CompositionAlgebra a Integer
treeDepth = CompositionAlgebra { leaf = const 1, composite = λx →  1 + maxInList x }

sumTree :: (Num a) ⇒ CompositionAlgebra a a
sumTree = CompositionAlgebra { leaf = id, composite = (+) } 

- y esto lattest sumTree es demasiado malo para GHC

Veo> + y, al igual que el C ++ operadores> y +. Así que no entiendo es GHC enojado conmigo sin mi el dar a ello Objetos implementar Opertor> / + o no.

En segundo lugar, debo admitir que estoy totalmente nebuloso sobre el sentido de => (diferente de -> ???). @ Y que parece ser como una guía para la coincidencia de patrones

¿Cómo corregir este código?

Y una última pregunta, También estoy tratando haciendo esto porque el patrón Composite pasó a ser el más importante para mí en C ++. Y, obviamente, veo que puede ser casi describe en una sola / dos líneas en Haskell (esto es verdaderamente increíble para mí).

Pero ¿cómo Haskell personas expresar el hecho de que la hoja y el constructor compuesto de composición puede tener algún tipo de interfaz de la misma? (Sé que no es la palabra buena ya que los datos no son mutables, pero espero que se puede adivinar de entender mi preocupación / meta)

este es el error total compilación;

src\Main.hs:27:79:
    Couldn't match expected type `[r]'
           against inferred type `Composition a'
    In the expression: y
    In the second argument of `map', namely `[y]'
    In the expression: map g [y]

src\Main.hs:30:20:
    Could not deduce (Ord a) from the context ()
      arising from a use of `>' at src\Main.hs:30:20-24
    Possible fix:
      add (Ord a) to the context of the type signature for `maxOfPair'
    In the expression: (x > y)
    In the expression: if (x > y) then (x) else (y)
    In the definition of `maxOfPair':
        maxOfPair x y = if (x > y) then (x) else (y)

src\Main.hs:41:0:
    Occurs check: cannot construct the infinite type: a = [a] -> [a]
    When generalising the type(s) for `sumTree'

Editar Así que esta es la versión final para catamorphism no binario

data Composant a = Leaf a
                 | Composite [Composant a]

data CompositionAlgebra a r = CompositionAlgebra { leaf      :: a →  r
                                             , composite :: [r] →  r }

foldComposition :: CompositionAlgebra a r →  Composant a →  r
foldComposition a@(CompositionAlgebra {leaf = f}) (Leaf x) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite ys) =  g(map(foldComposition a) ys)

maxOfPair :: Ord a ⇒ a →  a →  a
maxOfPair x y = if( x > y) 
                then (x) 
                else (y)

maxInList :: Ord a => [a] →  a
maxInList (x:xs) = maxOfPair x (maxInList xs)

treeDepth :: CompositionAlgebra a Integer
treeDepth = CompositionAlgebra { leaf = const 1, composite = λx →  1 + maxInList x }

addList :: Num a ⇒ [a] → a
addList (x:xs) = x + addList xs 

sumTree :: (Num a) ⇒ CompositionAlgebra a a
sumTree = CompositionAlgebra { leaf = id, composite = addList } 

Y de acuerdo con la respuesta válida a continuación:. Lo que estaba preguntando por Haskell equivalente de contratos Interfaces C ++ parece ser clases de tipos limitaciones

Así que el patrón de diseño compuesto se lograría mediante la aplicación de restricciones clase de tipos en la construcción de la composición A. Tal vez una nueva especializado de datos se debe definir. Pero debo aprender clases de tipos antes de hacer eso: -)

Answer 1

Hay algunos errores diferentes aquí, así que no estoy seguro de la mejor manera de tratar con él en el SO, pero qué diablos.

En el futuro, tratar de incluir más de los errores que ofrece GHC.

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite [y]) =  map g [y]

El foldCompose función tiene dos errores que puedo ver, sólo uno de los cuales serán capturados por el comprobador de tipo.

1. Esta coincidencia de patrones en (Composite [y]), que sólo igualará las listas de un elemento. Es probable que desee (Composite ys), que se une ys a toda la lista.

2. map g [y] no pasará el tipo de corrector, porque ya se ha definido g como tomar una lista de r, pero se están dando una lista de a.

   Con el fin de convertir un a a un r que necesita para aplicar su CompositionAlgebra a ella: g (map (foldComposition a) ys)

Así que me gustaría escribir esto como:

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite ys) = g (map (foldComposition a) ys)

Para su siguiente error:

maxOfPair :: a →  a →  a
maxOfPair x y = if( x > y) -- this doesnt please ghc either, Ordering trouble
                then (x) 
                else (y)

En Haskell, una variable de tipo (como a aquí) todo por su solitario puede ser rellenado con cualquier tipo en absoluto por la persona que llama, a elección de la persona que llama.

Esto significa, en su declaración de tipo que están alegando que la maxPair función trabajará para todos tipo de entrada. GHC se queja (a su manera) que el > operador no funciona para todos tipo, y por lo tanto se niega a compilar el programa.

Se tendrá que utilizar clases de tipos para resolver este problema. En Haskell, clases de tipos permiten la persona que llama recoger los tipos de uso, pero con algunas limitaciones. Recomiendo la lectura de un Haskell tutorial sobre clases de tipos .

El tipo de firma correcta sería:

maxOfPair :: Ord a => a →  a →  a

Lo que se aplica la restricción a la Ord a tipo.

Además, usted debe utilizar la función estándar max .

Answer 2

En segundo lugar, debo admitir que estoy completamente nebuloso sobre el sentido de => (diferente de -> ???) y @, que parece ser como una guía para la coincidencia de patrones.

consinder la elem función, que pone a prueba si una lista contiene un cierto valor. Se podría definir como

elem _ [] = False
elem x (y:ys) | x == y = True
              | otherwise = elem x ys

Lo que la firma tiene esta función? Aspecto del producto elem :: a -> [a] -> Bool. Sin embargo, el compilador se quejará porque usted escribió x == y, y no para cada a se define la función ==, sólo para aquellos que son a en el Ec clase de tipo . Así que hay que especificar algo como "Para todo a los que están en la Ec ...". Y precisamente por ello, tiene =>. Por lo que la firma correcta para elem es elem :: Eq a => a -> [a] -> Bool.

El @ le da la posibilidad de dar una estructura todo un nombre y modelar el partido en ella al mismo tiempo. P.ej. Si usted tiene la a@(x:xs) patrón y se llama a esa función con [1,2,3,4], entonces es a [1,2,3,4], xis 1 y xs es [2,3,4].