J'essayais de résoudre le Problème de Somme ultérieure de Sollection Maximal et est venu avec une solution NEATO
y f = f (y f)
msss' :: [Int] -> Int
msss' = y (\g' gmax lmax list -> if list == []
then gmax
else g' (max gmax lmax + head list)
(max 0 lmax + head list)
tail list)
3 Réponses :
Vous ne pouvez pas définir le combinateur Y comme celui de Haskell. Comme vous l'avez remarqué, cela entraîne un type infini. Heureusement, il est déjà disponible dans data.function comme correction , où il est défini à l'aide d'un laisse Reliure:
Il y a sûrement un moyen de définir + utiliser le combinateur y en ligne dans HASKELLL
@Leironknuckle: Il est possible si vous introduisez un nouveautype .
@Theironknoke: Bien sûr, juste en ligne la définition du correctif: (\ f -> let x = f x x)
Parce que le Combinator Y a besoin de types infinis, vous aurez besoin de solution de contournement comme celui-ci . < P> Mais j'écrirais votre MSSS comme une doublure comme ceci:
Notez que les types infinis n'apparaissent que dans des sous-ensembles faibles de systèmes de type HASKELL, tels que le système F, qui manquent à la fois des deux types récursifs et des types récursifs.
Eh bien, pensons-y pendant une minute. Quel type cette expression Lambda a-t-elle?
msss' = (\f -> let x = f x in x)
(\g' gmax lmax list -> case list of
[] -> gmax
(x:xs) -> g' (max gmax lmax + x) (max 0 lmax + x) xs
) 0 0
Quel est le problème avec la deuxième définition (dans laquelle le combinateur Y est défini séparément)? Vous devez juste corriger la définition de type ou ajouter
0 0 à la fin