haskell - sintaxis - ¿Por qué la longitud devuelve 1 para una tupla con 2 elementos y da un error para una tupla con más elementos?

funciones tuplas haskell

Question

Estoy estudiando a Haskell usando el libro " Programación de Haskell a partir de los primeros principios ", y hacia el final del Capítulo 4, "Tipos de datos básicos", me encontré con algo que me confundió. El libro menciona una length función y dice que funciona en Lists s. Todo está bien con eso, pero cuando intento esta función de length con varias Tuple , lo que veo me confunde:

Primero, veamos el tipo de length :

:t length
length :: Foldable t => t a -> Int

Bien, entonces leí arriba como "toma un Plegable, que creo que es una lista por conveniencia, y devuelve un Int, que es el número de elementos en la lista". De ahí mi primera confusión: ¿Por qué funciona lo siguiente?

length (1, 1)
1

Porque para mí, parece que acabo de pasar una tupla con dos elementos de length y devuelve 1. ¿Es la tupla una lista? ¿Es tupla plegable? Y por supuesto, ¿por qué 1 ?

Ahora voy un paso más allá:

length (1, 1, 1)

<interactive>:6:1:
    No instance for (Foldable ((,,) t0 t1))
      arising from a use of ‘length’
    In the expression: length (1, 1, 1)
    In an equation for ‘it’: it = length (1, 1, 1)

<interactive>:6:9:
    No instance for (Num t0) arising from the literal ‘1’
    The type variable ‘t0’ is ambiguous
    Note: there are several potential instances:
      instance Num Integer -- Defined in ‘GHC.Num’
      instance Num Double -- Defined in ‘GHC.Float’
      instance Num Float -- Defined in ‘GHC.Float’
      ...plus two others
    In the expression: 1
    In the first argument of ‘length’, namely ‘(1, 1, 1)’
    In the expression: length (1, 1, 1)

<interactive>:6:12:
    No instance for (Num t1) arising from the literal ‘1’
    The type variable ‘t1’ is ambiguous
    Note: there are several potential instances:
      instance Num Integer -- Defined in ‘GHC.Num’
      instance Num Double -- Defined in ‘GHC.Float’
      instance Num Float -- Defined in ‘GHC.Float’
      ...plus two others
    In the expression: 1
    In the first argument of ‘length’, namely ‘(1, 1, 1)’
    In the expression: length (1, 1, 1)

Otro intento:

length (1::Int, 1::Int, 1::Int)

<interactive>:7:1:
    No instance for (Foldable ((,,) Int Int))
      arising from a use of ‘length’
    In the expression: length (1 :: Int, 1 :: Int, 1 :: Int)
    In an equation for ‘it’: it = length (1 :: Int, 1 :: Int, 1 :: Int)

Pero lo siguiente funciona:

length (1::Int, 1::Int)
1

¿Hay alguna buena explicación para el comportamiento que estoy observando anteriormente? ¿Estoy leyendo mal el tipo de length ? ¿O hay algo más detrás de escena?

Answer 1

Me gusta la respuesta de danidiaz porque proporciona la intuición de alto nivel sobre cómo funciona la instancia Foldable para tuplas y lo que significa intuitivamente. Sin embargo, parece que todavía hay cierta confusión sobre la mecánica del mismo; así que en esta respuesta me enfocaré en los bits "detrás de escena". El texto completo de la instancia Foldable en cuestión está disponible en línea y tiene este aspecto:

instance Foldable ((,) a) where
    foldMap f (_, y) = f y
    foldr f z (_, y) = f y z

Ya puede ver desde esta instancia que la primera parte de cada tupla se ignora por completo en todos los métodos Foldable . Sin embargo, para completar la imagen, debemos mirar las definiciones de minimum y length . Dado que esta instancia no incluye definiciones de length minimum y minimum , deberíamos mirar las definiciones predeterminadas para estas. La declaración de clase para Foldable ve así (con bits irrelevantes eliminados):

class Foldable t where
    length :: t a -> Int
    length = foldl'' (/c _ -> c+1) 0

    foldl'' :: (b -> a -> b) -> b -> t a -> b
    foldl'' f z0 xs = foldr f'' id xs z0
      where f'' x k z = k $! f z x

    minimum :: forall a . Ord a => t a -> a
    minimum = fromMaybe (error "minimum: empty structure") .
       getMin . foldMap (Min #. (Just :: a -> Maybe a))

Así que ahora, ampliemos estas definiciones y veamos a dónde nos llevan.

length (a, b)
= { definition of length }
foldl'' (/c _ -> c+1) 0 (a, b)
= { definition of foldl'' }
foldr (/x k z -> k $! (/c _ -> c+1) z x) id (a, b) 0
= { definition of foldr }
(/x k z -> k $! (/c _ -> c+1) z x) b id 0
= { beta reduction }
id $! (/c _ -> c+1) 0 b
= { id $! e = e }
(/c _ -> c+1) 0 b
= { beta reduction }
1

Tenga en cuenta que la conclusión se cumple independientemente de lo que conectemos para a y b . Ahora hagamos lo minimum . Para nuestros propósitos, reemplazaremos (#.) Con (.) : La única diferencia es la eficiencia, que no nos importa para esta línea particular de razonamiento.

minimum (a, b)
= { definition of minimum }
( fromMaybe (error "minimum: empty structure")
. getMin
. foldMap (Min . Just)
) (a, b)
= { definition of (.) }
( fromMaybe (error "minimum: empty structure")
. getMin
) (foldMap (Min . Just) (a, b))
= { definition of foldMap }
( fromMaybe (error "minimum: empty structure")
. getMin
) ((Min . Just) b)
= { definition of (.) }
fromMaybe (error "minimum: empty structure")
(getMin (Min (Just b)))
= { definition of getMin }
fromMaybe (error "minimum: empty structure") (Just b)
= { definition of fromMaybe }
b

Answer 2

Te has encontrado con un Haskell causa célèbre que ha provocado mucha discusión y crujir de dientes.

Básicamente, a los efectos de Foldable (la clase de tipo que proporciona length ), las 2 tuplas no se consideran un contenedor de dos elementos, sino un contenedor de un elemento acompañado de algún contexto.

Puede extraer una lista de elementos de tipo a desde cualquier Foldable a . Observe que para las 2 tuplas, la variable de tipo del Foldable es la del segundo elemento de la tupla, y puede ser diferente del tipo del primer elemento.

Si tuviera una tupla (''c'',2) :: (Char,Int) , ¡no sería un misterio que no pudiera extraer dos Int s en ese caso! Pero cuando los tipos son iguales se vuelve confuso.

En cuanto a por qué falla la length (1::Int, 1::Int, 1::Int) , las 3 tuplas no tienen una instancia Foldable definida, pero quizás deberían tener una, por coherencia. Las 3 tuplas también tendrían longitud 1.

Por cierto, el Functor de Identity , que podría considerarse una especie de 1-tupla, también es Foldable y, por supuesto, tiene una longitud de 1.

¿Debería existir la instancia Foldable para tuplas? Creo que la filosofía subyacente a favor del sí es una, digamos, "plenitud". Si un tipo puede convertirse en una instancia de una clase de tipos de una manera legal y bien definida, debería tener esa instancia . Incluso si no parece muy útil y, en algunos casos, puede ser confuso.