06 maja 2013

Zliczyć krotność liter w ciągu znaków w Scali

Przyszło mi spędzać coraz więcej czasu ze Scalą ze względu na coraz trudniejsze zadania w szkoleniu Functional Programming Principles in Scala i tym razem trafiłem na ciekawy problem programistyczny, którego rozwiązanie dalekie jestbyło od doskonałości. Coś mi mówiło, że można ładniej, a na pewno skromniej (w sensie "w bardziej zwartej postaci").

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)) sorted
Obrzydlistwo!

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?

11 komentarzy:

  1. Mi wyszło coś takiego:

    l.groupBy(_._1).map(x => (x._1, x._2.foldLeft(0)(_ + _._2))).toList.sorted

    OdpowiedzUsuń
    Odpowiedzi
    1. Gratulacje! Ładne to, ale można ciut ładniej - podpowiedź: w map skorzytaj z tricku z foldLeft ("placeholder"), a foldLeft zamień na reduceLeft.

      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.

      Usuń
  2. Kosmetyczne do Antowego:

    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! :)

    OdpowiedzUsuń
    Odpowiedzi
    1. 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).

      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 :)

      Usuń
    2. 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ń
    3. Właśnie trafiłem na metodę mapValues! Zszedłem do 61 znaków! Pewnie da się jeszcze wycisnąć odrobinę z tego jednolinijkowca.

      Usuń
    4. import scalaz._;
      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?

      Usuń
    5. 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ń
    6. niezłe to |+| :-) ! Muszę wrzucić scalaz na listę rzeczy do obczajenia.

      Usuń
    7. l.groupBy(_._1).mapValues(_.map(_._2).sum).toList.sorted - warto było!

      Usuń
  3. Moja propozycja (widzę, że bardzo podobna do wersji msobkiewicz).

    l.groupBy(_._1).mapValues(_.unzip._2.sum).toList.sorted

    OdpowiedzUsuń