Załóżmy, że mamy nieuporządkowaną listę par znak-krotność (typu
List[(Char, Int)]
), w której można znaleźć pary dla tych samych liter, np.val l = List(('a',2), ('b',1), ('a',1), ('c',1), ('c', 3), ('e',3))Jak miałaby wyglądać funkcja, która przyjmuje listę, np.
l
powyżej, i "normalizuje" ją do postaci uszeregowanego (leksykograficznie) ciągu par, w których na drugiej pozycji jest suma wszystkich krotności dla danego znaku.Przy założeniu powyższej listy
l
otrzymalibyśmy wynik:List((a,3), (b,1), (c,4), (e,3))Początkowo napisałem takiego potworka, który nie tylko, że nie wyglądał, ale i posiadał błąd (patrz ostatni
map
z l.length
):(l groupBy { case (c, _) => c }).toList map (e => e._2) map (l => (l.head._1, l.length)) sortedObrzydlistwo!
Moje neurony nadawały na zwiększonej częstotliwości, kiedy ślęczałem nad tym problemem, a ostateczny wynik o mało co nie zrzucił mnie z krzesła! Przede wszystkim był mój i dodatkowo działał!
Nie podam jeszcze rozwiązania, aby nie psuć zabawy. Podpowiem, że w moim rozwiązaniu nie zabrakło miejsca dla
groupBy
, map
, funkcji anonimowych z case
oraz sum
i sorted
. W sumie 76 znaków, co wciąż nie zachwyca skromnością. A jak u Ciebie?
Mi wyszło coś takiego:
OdpowiedzUsuńl.groupBy(_._1).map(x => (x._1, x._2.foldLeft(0)(_ + _._2))).toList.sorted
Gratulacje! Ładne to, ale można ciut ładniej - podpowiedź: w map skorzytaj z tricku z foldLeft ("placeholder"), a foldLeft zamień na reduceLeft.
UsuńZastanawiam się jeszcze, na ile idiomatycznie byłoby usunięcie kilku kropek (które zastąpione przez spacje i nawiasy mogłyby nie wnieść wiele piękna).
I tutaj moje pytanie: czy istnieje funkcja rzutująca na pierwszy lub drugi element pary? Owe _1 i _2 jakoś do mnie nie przemawia i wolałbym first, second, itp.
Kosmetyczne do Antowego:
OdpowiedzUsuńl.groupBy(_._1).map(x => (x._1, x._2.map(_._2).sum)).toList.sorted
To samo w Clojure, trochę inną techniką, dla porównania:
(seq (apply merge-with + (map #(apply sorted-map %) l)))
Więcej spacji i nawiasów... wedle życzenia! :)
W map skorzystaj z "placeholder", jak w groupBy. Ciekawym również, na ile lepiej wyglądałby kod z funkcjami anonimowymi z dopasowywaniem wzorców (wyłącznie case).
UsuńPrzy okazji, dlaczego nikt nie obsłuży tego z reduceLeft...wyłącznie? Właśnie wpadłem na ten "genialny" pomysł podczas usypiania Maksymka :)
Też ładne (scalowe, na clojure nie mogę patrzeć :-), tylko że w tym podejściu trzeba przejść przez x._2 dwa razy - raz tworząc listę samych wartości i drugi raz sumując. foldLeft idzie po listach tylko raz.
UsuńWłaśnie trafiłem na metodę mapValues! Zszedłem do 61 znaków! Pewnie da się jeszcze wycisnąć odrobinę z tego jednolinijkowca.
Usuńimport scalaz._;
Usuńimport Scalaz._;
l.map(Map(_)).reduce(_ |+| _).toList.sorted
"|+|" jest tu odpowiednikiem clojurowego "merge-with +", niestety dochodzi import i zależność...
Samym zwijaniem można by tak np., ale niespecjalnie to czytelne w porównaniu z poprzednim:
l.foldLeft(Map[Char, Int]())((m, t) => m + (t._1 -> (m.getOrElse(t._1, 0) + t._2))).toList.sorted
Co Wy na to?
Z tym foldLeft zrobiłeś dokładnie jak ja to początkowo napisałem, więc działa zasada "great minds think alike" :-) Proponuję jednak przyjrzeć się mapValues. Rezultat może być warty zachodu.
Usuńniezłe to |+| :-) ! Muszę wrzucić scalaz na listę rzeczy do obczajenia.
Usuńl.groupBy(_._1).mapValues(_.map(_._2).sum).toList.sorted - warto było!
UsuńMoja propozycja (widzę, że bardzo podobna do wersji msobkiewicz).
OdpowiedzUsuńl.groupBy(_._1).mapValues(_.unzip._2.sum).toList.sorted