scala,recursion,types , How to write this recursive groupBy function in Scala


How to write this recursive groupBy function in Scala

Question:

Tag: scala,recursion,types

Recently I have come across a very useful groupBy function that Groovy has made available on Iterable:

public static Map groupBy(Iterable self, List<Closure> closures)

Which you can use to perform recursive groupBy on Lists and even Maps see example by mrhaki here

I would like to write a function that does the same in Scala. But having just started my Scala journey, I am kind of lost on how I should going about defining and implementing this method. Especially the generics side of the functions and return type on this method's signature are way beyond my level.

I would need more experienced Scala developers to help me out here.

Is this following signature totally wrong or am I in the ball park?

def groupBy[A, K[_]](src: List[A], fs: Seq[(A) ⇒ K[_]]): Map[K[_], List[A]]

Also, how would I implement the recursion with the correct types?


Answer:

This is simple multigroup implementation:

implicit class GroupOps[A](coll: Seq[A]) {
  def groupByKeys[B](fs: (A => B)*): Map[Seq[B], Seq[A]] =
    coll.groupBy(elem => fs map (_(elem)))
}

val a = 1 to 20

a.groupByKeys(_ % 3, _ % 2) foreach println

If you really need some recursive type you'll need a wrapper:

sealed trait RecMap[K, V]

case class MapUnit[K, V](elem: V) extends RecMap[K, V] {
  override def toString = elem.toString()
}
case class MapLayer[K, V](map: Map[K, RecMap[K, V]]) extends RecMap[K, V] {
  override def toString = map.toString()
}

out definition changes to:

implicit class GroupOps[A](coll: Seq[A]) {
  def groupByKeys[B](fs: (A => B)*): Map[Seq[B], Seq[A]] =
    coll.groupBy(elem => fs map (_(elem)))

  def groupRecursive[B](fs: (A => B)*): RecMap[B, Seq[A]] = fs match {
    case Seq() => MapUnit(coll)
    case f +: fs => MapLayer(coll groupBy f mapValues {_.groupRecursive(fs: _*)})
  }
}

and a.groupRecursive(_ % 3, _ % 2) yield something more relevant to question

And finally i rebuild domain definition from referred article:

case class User(name: String, city: String, birthDate: Date) {
  override def toString = name
}

implicit val date = new SimpleDateFormat("yyyy-MM-dd").parse(_: String)
val month = new SimpleDateFormat("MMM").format (_:Date)

val users = List(
  User(name = "mrhaki", city = "Tilburg"  , birthDate = "1973-9-7"),
  User(name = "bob"   , city = "New York" , birthDate = "1963-3-30"),
  User(name = "britt" , city = "Amsterdam", birthDate = "1980-5-12"),
  User(name = "kim"   , city = "Amsterdam", birthDate = "1983-3-30"),
  User(name = "liam"  , city = "Tilburg"  , birthDate = "2009-3-6")
)

now we can write

users.groupRecursive(_.city, u => month(u.birthDate))

and get

Map(Tilburg -> Map(Mar -> List(liam), Sep -> List(mrhaki)), New York -> Map(Mar -> List(bob)), Amsterdam -> Map(Mar -> List(kim), May -> List(britt)))


Related:


How to use the Akka ask pattern without blocking


scala,asynchronous,akka,future
Hi I have a actor which is responsible for fetching data from a database, turning it into a list and sending it back to the sender. I am using the ask pattern to receive response from my actor, because I don't want to use await.result because this approach will block...

Convert RDD[Map[String,Double]] to RDD[(String,Double)]


scala,apache-spark,rdd
I did some calculation and returned my values in a RDD containing scala map and now I want to remove this map and want to collect all keys values in a RDD. Any help will be appreciated....

Python RuntimeError: maximum recursion depth exceeded in cmp


python,list,dictionary,recursion
I have a complex data structure that I'm trying to process. Explanation of the data structure: I have a dictionary of classes. The key is a name. The value is a class reference. The class contains two lists of dictionaries. Here's a simple example of my data structure: import scipy.stats...

Scala running issue on eclipse


eclipse,scala
I configured everthing within eclipse for scala. I create a snippet to show you the issue, i can't see in run options run as scala application, i also tried to find my main class under build configuration option but i can't find it. How i can solve it?...

Scala first program issue


scala,recursion,case,frequency
I have just started to learn Scala after some experience with functional programming in other languages. def freq(c:Char, y:String, list:List[(Char,Int)]): List[(Char,Int)] = list match{ case _ => freq(c, y.filter(_ == c), list :: List((count(c,y),c))) case nil => list } In the above code I am getting an error when trying...

Scala unapplySeq extractor syntax


scala,pattern-matching,scala-2.11
I (inadvertently) came across a bit of pattern matching syntax I did not expect to compile and now cannot figure out. It appears related to unapplySeq. Note the case x List(_,_) part in this simple example: val xs = List(1, 2, 3) //> xs : List[Int] = List(1, 2, 3)...

Operand order in Scala List.prepend (::)


list,scala,operators
Odersky has brilliantly optimized Java syntax, enabling object calls without dots and parenthesis. I.e. instead of list.prepend(item), you now simply write list :: item, which also turns language operators into simple object methods. Here, List defines :: (prepend) operator. However, you normally write it vice-verse in Scala, using item ::...

Recursive Lag Column Calculation in SQL


sql,sql-server,recursion
I am trying to write a procedure that inserts calculated table data into another table. The problem I have is that I need each row's calculated column to be influenced by the result of the previous row's calculated column. I tried to lag the calculation itself but this does not...

T-SQL Ordering a Recursive Query - Parent/Child Structure


sql,tsql,recursion,order,hierarchy
I am trying (and failing) to correctly order my recursive CTE. My table consists of a parent-child structure where one task can relate to another on a variety of different levels. For example I could create a task (this is the parent), then create a sub-task from this and then...

How to effectively get indices of 1s for given binary string using Scala?


scala,functional-programming,higher-order-functions
Suppose we have a binary string such as 10010010. All I want is a function returning indices of 1s for that string: indicesOfOnes("10010010") -> List(0, 3, 6) indicesOfOnes("0") -> List() And what I implemented is: def indicesOfOnes(bs: String): List[Int] = { val lb = ListBuffer[Int]() bs.zipWithIndex.foreach { case (v, i)...

Scala rep separator for specific area of text


scala,parser-combinators
Imaging i've got following: --open Client: enter Nick Age 28 Rosewell, USA Client: enter Maria Age 19 Cleveland, USA --open-- I need a result close to the following: List(List(Nick, Age 28, Rosewell), List(Maria, Age19, Cleveland)) It can be as many clients inside open body as you can imagine, so the...

Recursion of Linked List


java,recursion,nullpointerexception,linked-list
When given an array of integers, I'm trying to change each element with the product of the integers before it. For example, int[] array = {2,2,3,4}; is now: {2, 4, 12, 48}; I added each element to a LinkedList, and I'm trying to do this recursively. This is what I...

My Scala program won't print anything


scala
Basically I'm trying to write a program that has a list of books and authors and then prints 2 things out, res1, which should print the book titles of the authors that have the name "Andrei" in it and res2 that should print the book titles that have the string...

implicit resolution for a function argument


scala,implicit,context-bound
I tried to implement mergesort in Scala. I got to the following: def mergeSort[A: Ordering](as: List[A]): List[A] = as match { case Nil => as case head :: Nil => as case _ => { val (l, r) = split(as) merge(mergeSort(l), mergeSort(r)) } } def split[A](as: List[A]): (List[A], List[A]) =...

How to unmarshall akka http request entity as string?


json,scala,akka-http
I'm trying to unmarshall request payload as string, but for some reason it's failing. My code: path("mypath") { post { decodeRequest { entity(as[String]) {jsonStr => //could not find implicit value for...FromRequestUnmarshaller[String] complete { val json: JsObject = Json.parse(jsonStr).as[JsObject] val jsObjectFuture: Future[JsObject] = MyDatabase.addListItem(json) jsObjectFuture.map(_.as[String]) } } } } } In...

Future yielding with flatMap


scala
Given Futures fa, fb, fc, I can use f: Function1[(A,B,C), Future[D]], to return a Future[D] either by: (for { a <- fa b <- fb c <- fc } yield (a,b,c)).flatMap(f) which has the unenviable property of declaring the variables a,b,c twice. or a.zip(b).zip(c).flatMap{ case (a, (b, c)) => f(a,...

Python recursive function not recursing


python,recursion
I'm trying to solve a puzzle, which is to reverse engineer this code, to get a list of possible passwords, and from those there should be one that 'stands out', and should work function checkPass(password) { var total = 0; var charlist = "abcdefghijklmnopqrstuvwxyz"; for (var i = 0; i...

R: recursive function to give groups of consecutive numbers


r,if-statement,recursion,vector,integer
Given a sorted vector x: x <- c(1,2,4,6,7,10,11,12,15) I am trying to write a small function that will yield a similar sized vector y giving the last consecutive integer in order to group consecutive numbers. In my case it is (defining groups 2, 4, 7, 12 and 15): > y...

Stopping condition on a recursive function - Haskell


string,function,haskell,if-statement,recursion
So, I have this function which aims to align the text on the left without cutting words(only white spaces). However my problem is that I cannot find a stopping condition of the function and it goes infinitely. f n "" = "" --weak condition f n s = if n...

Scala - Option Type Var Manipulation


scala,scala-option
I am working on an online exercise practicing Options and threads, both of which I have very little experience. The online exercise comes with a test suite, so right now I am trying to get my Option test cases to pass before I move on to the thread test cases....

Preventing a class instantiation in Scala using Factory Pattern [duplicate]


scala,factory-pattern
This question already has an answer here: How to check constructor arguments and throw an exception or make an assertion in a default constructor in Scala? 2 answers Suppose that I have the following class defined in Scala: class ClassA(val n: Int) { ... } I want to limit...

Collapse similar case statements in Scala


scala,functional-programming,pattern-matching
Is there an elegant way to do something like the following example using just one case statement? foobar match { case Node(Leaf(key, value), parent, qux) => { // Do something with parent & qux } case Node(parent, Leaf(key, value), qux) => { // Do something with parent & qux (code...

Scodec: Coproducts could not find implicit value for parameter auto: scodec.codecs.CoproductBuilderAuto


scala,scodec
I am trying to define an Scodec coproduct codec for communicating with an EELink GPS. Here is the code: import scodec.Codec import scodec.bits.ByteVector import scodec.codecs._ trait Message object Message { implicit val discriminated: Discriminated[ Message, Int ] = Discriminated(uint8) val codec: Codec[ Message ] = Codec.coproduct[ Message ].discriminatedByIndex(uint8) } case...

Access key from mapValues or flatMapValues?


scala,apache-spark
In Spark 1.3, is there a way to access the key from mapValues? Specifically, if I have val y = x.groupBy(someKey) val z = y.mapValues(someFun) can someFun know which key of y it is currently operating on? Or do I have to do val y = x.map(r => (someKey(r), r)).groupBy(_._1)...

Play Framework Form Error Handling


scala,playframework,playframework-2.3,playframework-2.4
This is my view file containing the form that has to filled in by the user: @helper.form(call) { @helper.input(resumeForm("surname"), '_label -> "Surname") { (id, name, value, args) => <input name="@name" type="text" value="@value" placeholder="Enter your surname"> } } This is my custom field constructor: @(elements: helper.FieldElements) @if(!elements.args.isDefinedAt('showLabel) || elements.args('showLabel) == true)...

Scala string replacement of entire words that comply with a pattern


string,scala,scala-collections,scala-string
In a string, how to replace words that start with a given pattern ? For instance replace each word that starts with "th", with "123", val in = "this is the example, that we think of" val out = "123 is 123 example, 123 we 123 of" Namely how to...

How to generalize the round methods


scala
I have the following four methods, using BigDecimal to round a number: private def round(input: Byte, scale: Int): Byte = { BigDecimal(input).setScale(scale, RoundingMode.HALF_UP).byteValue() } private def round(input: Short, scale: Int): Short = { BigDecimal(input).setScale(scale, RoundingMode.HALF_UP).shortValue() } private def round(input: Int, scale: Int): Int = { BigDecimal(input).setScale(scale, RoundingMode.HALF_UP).intValue() } private def...

Spray route get response from child actor


scala,akka,spray
I am trying to figure out how I can setup a Master Actor that calls the appropriate children, in support of some spray routes where I am trying to emulate db calls. I am new to akka / spray, so just trying to gain a better understanding of how you...

Reverse Linked List recursively, why it is wrong


recursion
Problem: Reverse a singly linked list recursively. I know how to solve this problem, but one of my recursive methods is wrong, I can not figure out what's wrong with this code. Could anyone figure out that? Thanks a lot! Test case: Input: [1,2,3] Output: [3,1] Expected: [3,2,1] public class...

Like clause not working with int column in slick


scala,slick,slick-2.0
Slick doesn't seem to support like clauses on int columns. The following code where Status.code is of int type doesn't seem to work. Would there be a workaround for this? val query = for { s <- Status if s.code like "1%" } yield (s) ...

Scala (Slick) HList splitting to case classes


scala,slick
currently I have a HList with more than 22 fields and now I want to split it to 2-3 case classes, is there an easy functional way to do it? Currently I use the following syntax: CaseClass1(c.head, c.tail.head, c.tail.tail.head, etc...) However that doesn't seem to be right since I have...

3 X 3 magic square recursively


c++,algorithm,math,recursion
I'm trying to find all possible solutions to the 3X3 magic square. There should be exactly 8 solutions. My code gets them all but there are a lot of repeats. I'm having a hard time tracking the recursive steps to see why I'm getting all the repeats. // This program...

How does ((a++,b)) work? [duplicate]


c,function,recursion,comma
This question already has an answer here: What does the comma operator `,` do in C? 8 answers In the below block of code, I am trying to understand how the line return reverse((i++, i)) is working. #include <stdio.h> void reverse(int i); int main() { reverse(1); } void reverse(int...

Retrieving TriangleCount


scala,apache-spark,spark-graphx
I'm trying to retrieve the amount of triangles from a graph using graphX. As I'm new to both Scala and graphX, I'm currently quite stuck. I'm creating a graph from an edgefile: 1 2 1 3 2 3 This should be 1 triangle. Next I'm using the build in function...

How to flatten a structure of embedded Set and Hash


ruby,recursion
I would like to convert an embedding structure into a flat one. An embedding structure is a set of 0 or more objects, such as: a string or a hash having some string as key and some other embedding structure as value. A flat structure is a set of arrays...

How to define a Regex in StandardTokenParsers to identify path?


regex,scala,parsing,lexical-analysis
I am writing a parser in which I want to parse arithmetic expressions like: /hdfs://xxx.xx.xx.x:xxxx/path1/file1.jpg+1 I want to parse it change the infix to postfix and do the calculation. I used helps from a part of code in another discussion as well. class InfixToPostfix extends StandardTokenParsers { import lexical._ def...

Spray microservice assembly deduplicate


scala,sbt,akka,spray,microservices
I'm using this template to develop a microservice: http://www.typesafe.com/activator/template/activator-service-container-tutorial My sbt file is like this: import sbt._ import Keys._ name := "activator-service-container-tutorial" version := "1.0.1" scalaVersion := "2.11.6" crossScalaVersions := Seq("2.10.5", "2.11.6") resolvers += "Scalaz Bintray Repo" at "https://dl.bintray.com/scalaz/releases" libraryDependencies ++= { val containerVersion = "1.0.1" val configVersion = "1.2.1"...

How to instantiate lexical.Scanner in a JavaTokenParsers class?


scala,parsing,lexical-scanner
I am writing a parser which inherits from JavaTokenParsers in that I have a function as follow: import scala.util.parsing.combinator.lexical._ import scala.util.parsing._ import scala.util.parsing.combinator.RegexParsers; import scala.util.parsing.combinator.syntactical.StdTokenParsers import scala.util.parsing.combinator.token.StdTokens import scala.util.parsing.combinator.lexical.StdLexical import scala.util.parsing.combinator.lexical.Scanners import scala.util.parsing.combinator.lexical.Lexical import...

Decremented value called in the recursion in Haskell


string,function,haskell,recursion,parameters
So, I have this function that aligns the text to the left for a given column width. I have already fixed some of its problems, but I am unable to make it not use the decremented parameter once it is called, but to return to the starting value of n....

PlayFramework: value as is not a member of Array[Byte]


scala,playframework
I want to make file download from a database using Play framework. But when I use this code I get this message: value as is not a member of Array[Byte] And if I change Ok(bytOfImage.as("image/jpg")) to Ok(bytOfImage) it works good but I get a file with a name: secondindex without...

Implicit Generic.Aux missing on conversion from Shapeless HList to case class


scala,shapeless,type-level-computation
I just recently started learning scala and today I decided I wanted to write a CSV parser that would load nicely into case classes but store the data in rows (lists) of Shapeless's HList object so that I could get some exposure to type-level programming. Here's what I have so...

Passing a function foreach key of an Array


scala,apache-spark,scala-collections,spark-graphx
I have an array like that : val pairs: Array[(Int, ((VertexId, Seq[Int]), Int))] which generates this output : (11,((11,ArraySeq(2, 5, 4, 5)),1)) (11,((12,ArraySeq(7, 7, 8, 2)),1)) (11,((13,ArraySeq(5, 9, 8, 7)),1)) (1,((1,ArraySeq(1, 2, 3, 4)),1)) (1,((4,ArraySeq(1, 5, 1, 1)),1)) I want to build a Graph for each pairs._1. That means for...

Scala slf4j dynamic file name


scala,logging,slf4j
I just successfully added Grizzled-SLF4J logger to my project using this link http://alvinalexander.com/scala/how-to-log-output-file-grizzled-slf4j-scala-simplelogger.properties But using this properties, there is no option to create dynamic file name: org.slf4j.simpleLogger.logFile = /tmp/myapp.log org.slf4j.simpleLogger.defaultLogLevel = info org.slf4j.simpleLogger.showDateTime = true org.slf4j.simpleLogger.dateTimeFormat = yyyy'/'MM'/'dd' 'HH':'mm':'ss'-'S org.slf4j.simpleLogger.showThreadName = true...

sum of Digits through Recursion


java,function,recursion,sum,digit
I am trying to make a recursive function which should return the sum of digits. The function should have only one argument. So far I have this; public int sumDigits(int n) { if(n%10 == n) // last digit remains return n; else{ int rightdigit; rightdigit = n%10; // taking out...

ZipList with Scalaz


list,scala,scalaz,applicative
Suppose I have a list of numbers and list of functions to apply to numbers: val xs: List[Int] = List(1, 2, 3) val fs: List[Int => Int] = List(f1, f2, f3) Now I would like to use an Applicative to apply f1 to 1, f2 to 2, etc. val ys:...

Zipping two arrays together with index in Scala?


arrays,scala,zip
I have two arrays populated with integers. They are the same size (val array1 and val array2). I want to fuse them together into tuples with their index as the third element. For example if we have val array1 = Array(5,2,6,2) and val array2 = Array(9,8,3,4) then I want to...

Implementing map on a tree using fold


scala,haskell
I am trying to implement a map using fold. I could do so in Haskell data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show) foldTree :: Tree a -> b -> (b -> a -> b -> b) -> b foldTree EmptyTree d _ =...

Is this definition of a tail recursive fibonacci function tail-recursive?


scala,f#,functional-programming,tail-recursion,continuation-passing
I've seen around the following F# definition of a continuation-passing-style fibonacci function, that I always assumed to be tail recursive: let fib k = let rec fib' k cont = match k with | 0 | 1 -> cont 1 | k -> fib' (k-1) (fun a -> fib' (k-2)...

SCALA: change the separator in Array


arrays,string,scala,delimiter
I have an Array like this. scala> var x=Array("a","x,y","b") x: Array[String] = Array(a, x,y, b) How do I change the separator comma in array to a :. And finally convert it to string like this. String = "a:x,y:b" My aim is to change the comma(separators only) to other separator(say,:), so...