¿Cómo puede uno razonar acerca de la complejidad algorítmica en Haskell?

7

En Haskell, la evaluación perezosa a menudo se puede usar para realizar cálculos eficientes de expresiones escritas de manera clara y concisa. Sin embargo, parece que el lenguaje en sí no proporciona suficientes detalles para determinar, en general, las necesidades de tiempo y espacio de una determinada pieza de código. La situación parece estar mitigada, hasta cierto punto, por el uso común de ghc, que, en mi opinión, ofrece algunas garantías más específicas relacionadas con la forma normal de cabeza débil. Pero si no me equivoco, el rendimiento real del código todavía puede ser bastante difícil de entender.

Por ejemplo, también usamos el polimorfismo para expresar funciones de una manera genérica, de nuevo sin sacrificar la claridad. Sin embargo, cuando se combinan con estructuras evaluadas de manera perezosa, las características de los dos idiomas parecen interactuar de manera sorprendente (para mí). Considera:

import Debug.Trace (trace)
tracePlus a b = trace (show a ++ "+" ++ show b) (a+b)
    -- This lets us try small integers to see how things get evaluated.
    -- Those tests can thereby reveal the asymptotic behavior of the code, without 
    -- needing to actually try bigger values.

class Sum a where
    one :: a
    add :: a -> a -> a

instance Sum Integer where
    one = 1
    add = tracePlus

fibSums_list :: (Sum a) => [a]
fibSums_list = one : one : zipWith add fibSums_list (tail fibSums_list)

fibS :: Int -> Integer
fibS = (fibSums_list !!)

Debo tener en cuenta que esto funciona bien si lo compilo con ghc -O2 . Sin embargo, cuando se ejecuta bajo ghci , se necesita una complejidad de tiempo exponencial para evaluar fibS . Sin embargo, usar una lista de números de Fibonacci del tipo [Integer] también funciona bien.

Entonces, una pregunta específica que tengo es: ¿hay una manera de volver a escribir fibSums_list y / o fibS , de manera que retenga el uso de la clase de tipo Sum , y todavía sea claramente una generalización de la ¿Secuencia de fibonacci, pero que también se evalúa eficientemente en ghci? ¿Dónde empiezo?

Y me pregunto si fallas similares le esperan incluso en el código compilado a través de ghc -O2 . Y si es así, ¿cómo los autores del código Haskell se encargan de eso?

Otra pregunta relacionada es ¿Cuándo es un buen momento para razonar sobre el rendimiento en Haskell? . Creo que mi pregunta es aún más fundamental; Ni siquiera entiendo cómo hacer la tarea de tal razonamiento. Hay una respuesta razonable allí, pero no tengo suficiente información específica para que pueda escribir un fibSums_list que funcione en ghci , y mucho menos una que tenga algún tipo de complejidad de tiempo garantizada.

    
pregunta Weston Markham 08.01.2018 - 00:29

1 respuesta

2

No hay respuesta que pueda proporcionar de manera integral El verdadero modo de razonar acerca de la complejidad algorítmica de Haskell. En parte, esto se debe a que gran parte del código de Haskell se basa en lo que el compilador realmente le hará en la práctica (GHC puede hacer que un programa sea más rápido o más lento de lo que cabría esperar). Pero puedo explicar la fuente de su sorpresa en el ejemplo que dio, y tal vez le sirva de guía sobre cómo Haskell evalúa las cosas.

  

Por ejemplo, también usamos el polimorfismo para expresar funciones en una   Moda genérica, de nuevo sin sacrificar la claridad. Sin embargo cuando   combinadas con estructuras evaluadas perezosamente, las dos características del lenguaje   Parecen interactuar de maneras que son (para mí) sorprendentes.

Si inspeccionas el IR central para el código que escribiste para fibSums_list , se revelarán algunas cosas:

fibSums_list :: forall a. Sum a => [a]
fibSums_list
  = \ (@ a) ($dSum :: Sum a) ->
      : (one $dSum)
        (: (one $dSum)
           (zipWith
              (add $dSum) (fibSums_list $dSum) (tail (fibSums_list $dSum))))
  1. fibSums_list se reduce a una función, no a un valor!
  2. Un valor que describe Sum a es en realidad un parámetro de la función.
  3. Cuando escribes fibSums_list en el cuerpo, en realidad estás llamando a la función recursivamente con el argumento implícito.

Relacionando esto con el lenguaje, cualquier "valor" polimórfico tiene que ser bien escrito por sí mismo. Por lo tanto, el significado de fibSums_list es "dame un thunk a través del cual puedo calcular este valor en el entorno de clase dado". Un poco de tiempo para resolver esto en papel debería convencerlo de que compartir el procesador no es estrictamente necesario para obtener un resultado correcto al salir de un índice.

Por lo tanto, una mejor manera de pensar acerca de las funciones polimórficas ad-hoc podría ser mirarlas como OOP-esque factories para construir sus valores reales a partir de un entorno de clase de tipos. Con eso en mente, puedes obtener la lista infinita que deseas:

fibSums_list :: Sum a => [a]
fibSums_list = fibz
  where fibz = one : one : zipWith add fibz (tail fibz)

Ahora, cuando miramos el Núcleo, podemos ver claramente el comportamiento de "fábrica".

fibSums_list :: forall a. Sum a => [a]
fibSums_list
  = \ (@ a) ($dSum :: Sum a) ->
      letrec {
        fibz :: [a]
        fibz
          = break<3>()
            : (one $dSum)
              (break<2>()
               : (one $dSum)
                 (break<1>() zipWith (add $dSum) fibz (break<0>() tail fibz))); } in
      break<4>(fibz) fibz

El valor fibz existe dentro de fibSums_list , por lo que el entorno de clase ya está establecido. Eso significa que fibz no es una función, sino un valor con un procesador consistente que se expandirá perezosamente.

Puede ver esto en acción, calculando fibS 100 en GHCI aquí .

Sospecho que la razón por la que GHC's -O2 produce código rápido para usted es porque se especializa fibSums_list y lo reescribe para que el entorno de clase se corrija desde el punto de vista de fibS . Entonces se vuelve como si hubieras escrito fibSums_list :: [Integer] y todo se vuelve mucho más simple.

    
respondido por el Alex Reinking 14.11.2018 - 15:39

Lea otras preguntas en las etiquetas