Sur Hackage, je vois que groupBy L'implémentation de est la suivante :

groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _  []           =  []
groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
                           where (ys,zs) = span (eq x) xs

Ce qui signifie que le prédicat eq tient entre deux éléments quelconques de chaque groupe. Exemples:

> difference_eq_1 = ((==1).) . flip (-)
> first_isnt_newline = ((/= '\n').) . const
>
> Data.List.groupBy difference_eq_1 ([1..10] ++ [11,13..21])
[[1,2],[3,4],[5,6],[7,8],[9,10],[11],[13],[15],[17],[19],[21]]
>
> Data.List.groupBy first_isnt_newline "uno\ndue\ntre"
["uno\ndue\ntre"]

Que se passe-t-il si, à la place, je souhaite grouper des éléments de telle sorte que le prédicat tienne entre toute paire d'éléments consécutifs, de sorte que les résultats ci-dessus soient les suivants ?

[[1,2,3,4,5,6,7,8,9,10,11],[13],[15],[17],[19],[21]]
["uno\n","due\n","tre"]

Je l'ai écrit moi-même, et ça a l'air un peu moche

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy' p = foldr step []
  where step elem [] = [[elem]]
        step elem gs'@((g'@(prev:g)):gs)
          | elem `p` prev = (elem:g'):gs
          | otherwise = [elem]:gs'

Je me demandais donc si une telle fonction existait déjà et je ne la trouve tout simplement pas.

En ce qui concerne la deuxième utilisation, Data.List.groupBy first_isnt_newline, où le prédicat binaire ignore essentiellement le deuxième argument et applique un prédicat unaire au premier, je viens de découvrir que Data.List.HT.segmentAfter unary_predicate fait le travail, où unary_predicate est la négation du prédicat unaire dans lequel la sortie de const est transmise. En d'autres termes Data.List.groupBy ((/= '\n').) . const === Data.List.HT.segmentAfter (=='\n').

6
Enlico 7 oct. 2020 à 19:36

1 réponse

Meilleure réponse

Il existe un package groupBy qui fait exactement cela.

Mais voici une autre façon de le mettre en œuvre :

  • Zip la liste avec sa queue pour tester le prédicat sur les éléments adjacents

  • Générer un « index de groupe » en scannant le résultat et en incrémentant le groupe chaque fois que le prédicat est faux

  • Grouper par l'indice

  • Supprimer les index

groupByAdjacent :: (a -> a -> Bool) -> [a] -> [[a]]
groupByAdjacent p xs
  = fmap (fmap fst)
  $ groupBy ((==) `on` snd)
  $ zip xs
  $ scanl' (\ g (a, b) -> if p a b then g else succ g) 0
  $ zip xs
  $ drop 1 xs

Pour une entrée comme [1, 2, 3, 10, 11, 20, 30], le prédicat renverra [True, True, False, True, False, False] et les indices de groupe résultants seront [0, 0, 0, 1, 1, 2, 3].

Le balayage peut également être écrit sans point comme scanr (bool succ id . uncurry p) 0, car la direction du balayage n'a pas d'importance (bien que les indices de groupe soient inversés). L'index de groupe peut être pratique ou simplement plus lisible à conserver sous forme d'entier, mais il pourrait plutôt s'agir d'un Bool, car la taille minimale d'un groupe est de 1 : l'argument fonctionnel de l'analyse serait bool not id . uncurry p, qui peut être simplifié en (==) . uncurry p. Et plusieurs de ces parties pourraient être intégrées dans des fonctions réutilisables, comme zipNext = zip <*> drop 1, mais je les ai intégrées par souci de simplicité.

3
Jon Purdy 7 oct. 2020 à 17:51