Ninety-Nine Scala Problems

相似文件 换一批

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

S-99: Ninety-Nine Scala Problems

These are an adaptation of the Ninety-Nine Prolog Problems written by Werner Hett at the Berne University of Applied Sciences in Berne, Switzerland. I (Phil Gold) have altered them to be more amenable to programming in Scala. Feedback is appreciated, particularly on anything marked TODO.

The problems have different levels of difficulty. Those marked with a single asterisk (*) are easy. If you have successfully solved the preceeding problems you should be able to solve them within a few (say 15) minutes. Problems marked with two asterisks (**) are of intermediate difficulty. If you are a skilled Scala programmer it shouldn't take you more than 30-90 minutes to solve them. Problems marked with three asterisks (***) are more difficult. You may need more time (i.e. a few hours or more) to find a good solution. The difficulties were all assigned for the Prolog problems, but the Scala versions seem to be of roughly similar difficulty.

Your goal should be to find the most elegant solution of the given problems. Efficiency is important, but clarity is even more crucial. Some of the (easy) problems can be trivially solved using built-in functions. However, in these cases, you learn more if you try to find your own solution.

Solutions are available by clicking on the link at the beginning of the problem description.

[I don't have example solutions to all of the problems yet. I'm working on getting them all done, but in the meantime, contributed solutions, particularly from seasoned Scala programmers would be appreciated. If you feel a particular problem can be solved in a better manner than I did, please let me know that, too. <PMG>]

本帖隐藏的内容

99-Scala-Problems-master.zip (110.01 KB)

2017-1-25 09:54:15 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Problems problem SCALA Nine LEM difficulty University different anything problems

1. // P01 (*) Find the last element of a list.
   
2. //     Example:
   
3. //     scala> last(List(1, 1, 2, 3, 5, 8))
   
4. //     res0: Int = 8
   
5. 
   
6. // The start of the definition of last should be
   
7. //     def last[A](l: List[A]): A = ...
   
8. // The `[A]` allows us to handle lists of any type.
   
9. 
   
10. object P01 {
    
11.   // There are several ways to solve this problem.  If we use builtins, it's very
    
12.   // easy.
    
13.   def lastBuiltin[A](ls: List[A]): A = ls.last
    
14. 
    
15.   // The standard functional approach is to recurse down the list until we hit
    
16.   // the end.  Scala's pattern matching makes this easy.
    
17.   def lastRecursive[A](ls: List[A]): A = ls match {
    
18.     case h :: Nil  => h
    
19.     case _ :: tail => lastRecursive(tail)
    
20.     case _         => throw new NoSuchElementException
    
21.   }
    
22. }

复制代码

1. // P02 (*) Find the last but one element of a list.
   
2. //     Example:
   
3. //     scala> penultimate(List(1, 1, 2, 3, 5, 8))
   
4. //     res0: Int = 5
   
5. 
   
6. object P02 {
   
7.   // Again, with builtins this is easy.
   
8.   def penultimateBuiltin[A](ls: List[A]): A =
   
9.     if (ls.isEmpty) throw new NoSuchElementException
   
10.     else ls.init.last
    
11. 
    
12.   // But pattern matching also makes it easy.
    
13.   def penultimateRecursive[A](ls: List[A]): A = ls match {
    
14.     case h :: _ :: Nil => h
    
15.     case _ :: tail     => penultimateRecursive(tail)
    
16.     case _             => throw new NoSuchElementException
    
17.   }
    
18.   
    
19.   
    
20.   // Just for fun, let's look at making a generic lastNth function.
    
21. 
    
22.   // An obvious modification of the builtin solution works.
    
23.   def lastNthBuiltin[A](n: Int, ls: List[A]): A = {
    
24.     if (n <= 0) throw new IllegalArgumentException
    
25.     if (ls.length < n) throw new NoSuchElementException
    
26.     ls.takeRight(n).head
    
27.   }
    
28. 
    
29.   // Here's one approach to a non-builtin solution.
    
30.   def lastNthRecursive[A](n: Int, ls: List[A]): A = {
    
31.     def lastNthR(count: Int, resultList: List[A], curList: List[A]): A =
    
32.       curList match {
    
33.         case Nil if count > 0 => throw new NoSuchElementException
    
34.         case Nil              => resultList.head
    
35.         case _ :: tail        =>
    
36.           lastNthR(count - 1,
    
37.                    if (count > 0) resultList else resultList.tail,
    
38.                    tail)
    
39.       }
    
40.     if (n <= 0) throw new IllegalArgumentException
    
41.     else lastNthR(n, ls, ls)
    
42.   }
    
43. }

复制代码

1. // P03 (*) Find the Kth element of a list.
   
2. //     By convention, the first element in the list is element 0.
   
3. //
   
4. //     Example:
   
5. //     scala> nth(2, List(1, 1, 2, 3, 5, 8))
   
6. //     res0: Int = 2
   
7. 
   
8. object P03 {
   
9.   // Trivial with builtins.
   
10.   def nthBuiltin[A](n: Int, ls: List[A]): A =
    
11.     if (n >= 0) ls(n)
    
12.     else throw new NoSuchElementException
    
13. 
    
14.   // Not that much harder without.
    
15.   def nthRecursive[A](n: Int, ls: List[A]): A = (n, ls) match {
    
16.     case (0, h :: _   ) => h
    
17.     case (n, _ :: tail) => nthRecursive(n - 1, tail)
    
18.     case (_, Nil      ) => throw new NoSuchElementException
    
19.   }
    
20. }

复制代码

1. // P04 (*) Find the number of elements of a list.
   
2. //     Example:
   
3. //     scala> length(List(1, 1, 2, 3, 5, 8))
   
4. //     res0: Int = 6
   
5. 
   
6. object P04 {
   
7.   // Builtins.
   
8.   def lengthBuiltin[A](ls: List[A]): Int = ls.length
   
9. 
   
10.   // Simple recursive solution.
    
11.   def lengthRecursive[A](ls: List[A]): Int = ls match {
    
12.     case Nil       => 0
    
13.     case _ :: tail => 1 + lengthRecursive(tail)
    
14.   }
    
15. 
    
16.   // Tail recursive solution.  Theoretically more efficient; with tail-call
    
17.   // elimination in the compiler, this would run in constant space.
    
18.   // Unfortunately, the JVM doesn't do tail-call elimination in the general
    
19.   // case.  Scala *will* do it if the method is either final or is a local
    
20.   // function.  In this case, `lengthR` is a local function, so it should
    
21.   // be properly optimized.
    
22.   // For more information, see
    
23.   // http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html
    
24.   def lengthTailRecursive[A](ls: List[A]): Int = {
    
25.     def lengthR(result: Int, curList: List[A]): Int = curList match {
    
26.       case Nil       => result
    
27.       case _ :: tail => lengthR(result + 1, tail)
    
28.     }
    
29.     lengthR(0, ls)
    
30.   }
    
31. 
    
32.   // More pure functional solution, with folds.
    
33.   def lengthFunctional[A](ls: List[A]): Int = ls.foldLeft(0) { (c, _) => c + 1 }

复制代码

Thanks.
Ninety-Nine Scala Problems