Soy nuevo en la programación funcional y el lenguaje haskell. Estoy tratando de determinar la longitud de la serie contigua más larga de elementos en una lista dependiendo de una función de predicado. La función se ve así:

 longestSequence :: (a -> Bool) -> [Int] -> Int

Cuando lo llamo así:

 longestSequence (\x -> x >= 10) [1,44,33,22,2,3,55,66,66,77,88,99]

Debería darme como solución 6.

Mi solución hasta ahora es:

longestSequence :: (a -> Bool) -> [a] -> Int
longestSequence p [] = 0
longestSequence p (x:xs) 
  | (p x) = 1 + (longestSequence p xs)
  | otherwise = longestSequence p xs

¿Alguna pista o idea de cómo puedo resolver este problema?

2
Oni1 30 dic. 2016 a las 04:06

3 respuestas

La mejor respuesta

Intenta factorizar los subproblemas más pequeños. Para este ejemplo, la estrategia general podría ser así:

  1. Convierta la lista dada en una lista [Bool] donde una entrada es True si la entrada correspondiente satisface el predicado. Es decir, escribir una función (Int -> Bool) -> [Int] -> [Bool]
  2. Agrupe los valores consecutivos True y False. Es decir, escriba una función [Bool] -> [[Bool]]. Es posible que desee ver {{ X3}}.
  3. Filtre los grupos False: [[Bool]] -> [[Bool]]
  4. Para cada una de las listas internas, cuente su longitud. [[Bool]] -> [Int]
  5. Encuentre el máximo de esas longitudes: [Int] -> Int

Luego solo tiene que componer esas funciones y listo. Para 1. y 4. querrá usar la función map :: (a -> b) -> [a] -> [b]. Si ya conoce map, simplemente utilícelo. Si no lo hace, sugeriría escribir eso usted mismo también.

Algunas de las firmas de tipo para las funciones que proporcioné son demasiado específicas. Tal vez intente generalizarlos un poco donde pueda.

5
amalloy 30 dic. 2016 a las 01:46

En las guardias, p x y otherwise parte tienen problemas.

(p x) = 1 + (longestSequence p xs) no siempre es cierto, si el siguiente elemento de x no tiene predicción p, no se puede agregar 1

otherwise = longestSequence p xs no es cierto si la secuencia más larga actual es más larga que la secuencia restante

Una posible solución es mantener la longitud máxima y la longitud actual

longestSequence :: (a -> Bool) -> [a] -> Int
longestSequence p x = ls x 0 0
  where
    ls [] mx cur = max mx cur
    ls (x:xs) mx cur
        | p x = ls xs mx (cur+1)
        | otherwise = ls xs (max mx cur) 0
3
delta 30 dic. 2016 a las 01:46

A menudo puede usar fold, que es más simple que la recursividad, y en este caso, queremos usar scanl, que es como foldl, excepto que mantiene la lista completa.

Lo siguiente itera a través de la lista, incrementando el recuento de cada elemento que coincide con el predicado. Si encuentra uno que no coincide, restablece el recuento a cero. Al final, encuentra el máximo de la lista resultante.

longestSequence p = maximum . scanl (\count x -> if (p x) then count + 1 else 0) 0

Para su entrada de ejemplo de [1,44,33,22,2,3,55,66,66,77,88,99] y el predicado de (\x -> x >= 10), el scanl producirá una salida de [0,0,1,2,3,0,0,1,2,3,4,5,6]. Tomar el máximo de esta lista da 6, y puede ver que el máximo ocurre al final de la entrada, y también los ceros en la lista donde el predicado no coincide.

Por cierto, estoy totalmente de acuerdo con jpath sobre dividir el problema en partes pequeñas. He visto a personas resolver problemas similares con un fold al meter el cálculo max dentro del parámetro \count con una tupla, pero eso hace que sea mucho más difícil de leer. Eso también es lo que hace que las soluciones recursivas de una sola función como la suya sean difíciles de entender, por cierto. Demasiado para hacer un seguimiento de una vez, por lo que es difícil ver dónde y cómo encajar en la parte de restablecimiento a cero.

1
Karl Bielefeldt 30 dic. 2016 a las 04:50