types - superponer - La variable tipo para unificar ocurre en tipo

superponer graficas en r

Question

Tengo una función para reconstruir un árbol de 2 listas. Devuelvo una lista en todas las ramas, pero recibo un error que no entiendo. Pero supongo que tiene que ver con los tipos de devolución.

El error es este:

Can''t unify ''''a with ''''a list (Type variable to be unified occurs in type) Found near recon
( ::( preoH, preoT), ::( inoH, ...))
Exception- Fail "Static errors (pass2)" raised

La línea en la que se produce el error es el título de la definición de función fun recon (preoH::preoT, inoH::inoT) =

¿Qué significa exactamente ese error y por qué ocurre?

(* Reconstruts a binary tree from an inorder and a preorder list. *)
fun recon (preoH::preoT, inoH::inoT) =
(* Case 0: Leaf reached*)
if
preoT = [] andalso inoT = [] andalso preoH = inoH
then
[preoH]
else
let
(* split the list of nodes into nodes to the left and nodes to the
right of preoH; ST stands for subtree *)
val (inoLST, inoRST) = splitat (inoH::inoT, preoH)
val (preoLST, preoRST) = splitafter (preoT, last(inoLST))
in
(* Case 1: Unary branch encountered, make preoH the parent node of the
subtree and combine the left and right preorder and inorder lists*)
if
length(inoLST) <> length(preoLST)
then
[preoH, recon (preoLST@preoRST, inoLST@inoRST)]
(* Case 2: Binary branch encountered, proceed as normal *)
else
[recon (preoLST, inoLST), preoH, recon (preoRST, inoRST)]
end;

Answer 1

Unificar una variable con algo significa encontrar un valor para la variable que iguala ese algo. Por ejemplo, podemos unificar algo simple como (usaré un triple igual para significar que los dos términos deben ser iguales):

a === int

El resultado de la unificación es un valor que podemos sustituir por a. En este caso, podemos sustituir int por a y la ecuación se mantendrá (es similar a resolver sistemas de ecuaciones en matemáticas):

a: int
-----------
int === int

O podemos unificar una ecuación un poco más complicada:

a -> int === bool -> b

Aquí, necesitamos encontrar los valores que deben sustituirse por a y b para que la ecuación se mantenga. Estos son bool para a y int para b :

a: bool
b: int
---------------------------
bool -> int === bool -> int

Espero que ya tengas la idea. En su caso, el compilador tiene que unificar esto:

a === a list

Bueno, es ''''a vez de solo a mensaje de error, pero podemos descuidar eso por el momento. La cuestión es que, debido a que a aparece en ambos lados, la ecuación no es unificable, por lo tanto, la sugerencia en el mensaje de error (énfasis mío) "Tipo de variable a unificar se produce en tipo ". Si dijéramos que a debe ser a list y reemplazamos a con ambas partes, obtendríamos esto:

a list === a list list

No hemos eliminado la variable que necesitamos resolver y no lo haremos pronto. Es por eso que el compilador barfs, conduce a un bucle infinito y una simple comprobación de que la variable no ocurre en ambos lados de la ecuación es una buena manera de evitar ese bucle.

¿Por qué sucede en tu caso? La versión corta es que estás tratando de representar un árbol usando listas anidadas y el sistema de tipos de SML no puede manejar eso. El árbol que intentas construir en términos de listas se parece a esto:

[[a], a, [a]]

Donde a es una variable de tipo genérico. Las listas son contenedores homogéneos, solo pueden contener valores de un solo tipo, lo que significa que [a] y a deben ser del mismo tipo, es decir:

a === a list

Y ya he explicado por qué esto conduce a un error.

La solución es usar un datatype de datatype recursivo para representar árboles, como este:

datatype ''a tree =
Leaf
| Node of { value : ''a, left: ''a tree, right: ''a tree }

Esto funciona porque nos permite definirlo recursivamente, es decir, el tipo de las hojas son tree mismos. Su función de recon debe tener ''''a tree como su tipo de devolución.

Con suerte, está un poco más claro ahora.

Answer 2

1. Ionut dio una explicación exhaustiva de cómo funciona la unificación de tipos, así que aquí hay una pista:

   [preoH, recon (preoLST@preoRST, inoLST@inoRST)]

   El primer elemento tiene tipo ''a y el segundo elemento tiene tipo '' una lista .

   [recon (preoLST, inoLST), preoH, recon (preoRST, inoRST)]

   El segundo elemento tiene tipo ''a y el primer y tercer elemento tienen tipo '' una lista .

2. Cuando comprueba si las listas están vacías, considere usar null preoT , o maneje el caso usando la coincidencia de patrones.