Exercise-01 Solution

Moderator: Konzepte der Programmiersprachen

saifposinc
Neuling
Neuling
Beiträge: 6
Registriert: 10. Dez 2018 19:20

Exercise-01 Solution

Beitrag von saifposinc » 14. Jan 2019 23:52

Hello,

I'm not understanding this part of the code where it was asked to write a recursive function 'sum' that sums up the elements of a list of numbers:

def sum(l: List[Int]): Int = l match {
case Nil => 0
case x :: xs => x + sum(xs)
}

Given, I know how Scala List & match-case work, also know '::' prepends an element into the List. The question is how 'case x :: xs => x + sum(xs)' is working.
'sum(xs)'- is called again recursively, but at first 'sum()' was called for the List 'l', is 'xs' a list? how?

Thanks,
-Saif

HerrmannIV
Neuling
Neuling
Beiträge: 7
Registriert: 18. Jun 2013 14:41

Re: Exercise-01 Solution

Beitrag von HerrmannIV » 15. Jan 2019 00:05

Hi,
It bascially is like
"if l is a list built like x :: xs then sum(l) = x + sum(xs)", where x is head (i.e. first element of l) and xs is tail (i.e. the remaining elements, as a list, of l)
I hope i am still making sense at that time ;) Does that answer your question?
BG

saifposinc
Neuling
Neuling
Beiträge: 6
Registriert: 10. Dez 2018 19:20

Re: Exercise-01 Solution

Beitrag von saifposinc » 15. Jan 2019 00:24

Hi,

Related to your answer, I can rewrite it as:

def sum(l: List[Int]): Int = l match {
case Nil => 0
case x => x.head + sum(x.tail) //case x :: xs => x + sum(xs)
}
& works fine

But how '::' works here? I only know '::' prepends element in the List. Would you break down a bit more how it is working here.

0b101101101
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 179
Registriert: 15. Apr 2015 18:24

Re: Exercise-01 Solution

Beitrag von 0b101101101 » 15. Jan 2019 01:26

Here is another way to look at the problem:

A List is either Nil or Cons(x, xs):

class List[A]
case class Nil[A] extends List[A]
case class Cons[A](x: A, xs: List[A]) extends List[A]

Note, in scala Cons was called :: . So its actually something like:

class List[A]
case class Nil[A] extends List[A]
case class ::[A](x: A, xs: List[A]) extends List[A]

Think of x :: xs is a nice way to write something like Cons(x, xs) without parenthesis.


As always with case classes and matches:
The case classes defined all the possibilities we have to handle,
the corresponding match then describes how we handle all possibilities:

x match {
case Nil =>
case Cons(x, xs) =>
}

Or with the more beautiful ::

x match {
case Nil =>
case x :: xs =>
}

Antworten

Zurück zu „Konzepte der Programmiersprachen“