over 1 year ago

前言

Scala是具備函數式編程(Functional Programming)特性的程式語言,因此如何使用函數是學習Scala必要的過程,在這個章節中我們將會了解

  • 如何宣告函數?
  • Closures(大陸將Cloures翻譯成閉包)
  • 使用val宣告函數

如何宣告函數?

def function_name(p1:T1, p2:T2,...,pN:TN):T={
    //do something...
}

其中def為保留字,用來宣告函數;p1,...,pN表示此函數所需要的參數;T表示回傳的結果類型,在Scala中是不需要使用return這個保留字,因為它會自動判斷最後一行程式碼的回傳的類型, T亦可以省略,讓Scala自動判斷類型,如

def function_name(p1:T1, p2:T2,...,pN:TN)={
    //do something...
}

注意!!參數類型是不可省略的!!!
接下來讓我們來看看以下幾個簡單的實例吧!!!

Example 1

定義一個平方(square)函數.
input: 2
output: 4

def square(x:Int):Int= ???

Answer 1
def square(x:Int):Int= x*x
Example 2

定義一個判斷是否為奇數的函數.
input: 2
output: false

def isOdd(x:Int):Boolean= ???
Answer 2
def isOdd(x:Int):Boolean= x%2==1

補充: %為取餘數的運算子,如x%2表示x除以2的餘數

Function Closures

closures在計算機中可以理解成變量的有效範圍,如

def A(a:T)={
    val b=a
    println(b)  
    a
}
println(b)  

在函數A中我們宣告了變量bb的有效範圍只會在函數A中,我們最後一行寫的println(b)將會導致程式出錯,對編譯器來說這時候的b是還未被定義的。

在Scala中特別的地方是可以在函數內再另行宣告一個子函數,而子函數也具備closures的性質,

def func(a:T1)={
    def subFunc(b:T2)=???
  
    //do something
 
}
    

subFunc的有效範圍僅在func中而己,一旦離開func使用subFunc,編譯器將會出現錯誤。
現在讓我們來看看下面幾個例子

Example 3

定義一個平方和(sum of squares)函數.
input: 2, 3
output: 13

def sumOfSquares(x:Int,y:Int):Int= ???

Answer 3
//Answer3.1
def square(x:Int):Int= x*x 
def sumOfSquares(x:Int,y:Int):Int= square(x)+square(y)

//Answer3.2
def sumOfSquares(x:Int,y:Int):Int= {
    def square(x:Int):Int= x*x
    square(x)+square(y)
}

Answer3.1與Answer3.2兩個方法均可正確執行,差別在於
Answer3.1在sumOfSquares中呼叫外部square,其他函數可以重複使用square函數;
Answer3.2則是在sumOfSquares宣告square,若其他函數需要使用square,則須重新宣告

使用val宣告函數

在Scala中有另一種使用val宣告函數的方式,讓我們直接來看看讓怎麼做

val func:T1=> TRes = x=>//do something!!

其中=>念作to,

以上程式碼val func:T1=> TRes表示宣告一個參數類型為T1(只有一個參數!!!),回傳類型為TRes的函數,且此函數名為func
注意!!T1=> TRes不可以省略,編譯器是無法判斷函數類型的!!

另外x=>//do something!!x是可隨意命名的=>後面可以實現此函數功能。
為了讓大家更清楚這種宣告方式,我們將以上的Example1~2改用val的方式來實現吧!!

// Example 1
val square:Int=>Int= x=>x*x
// Example 2
val isOdd:Int=>Boolean = x=> x%2==1

看到這裡大家可能會有個疑問-像sumOfSquares這種多參數的函數,應該怎麼使用val宣告呢???
基本上Scala對於多參數函數的宣告採用了與Tuple相同的宣告方式(Tuple的使用我們將會在集合的章節做詳細的討論),如下

val func:(T1,T2)=> TRes = (x1,x2)=>//do something!!

特別注意(T1,T2)表示為第一個參數(x1)類型為T1, 第二個參數(x2)類型為T2; 超過2個以上的參數則以此類推,如下

val func:(T1,...,TN)=> TRes = (x1,...,xN)=>//do something!!

注意!!Scala中Tuple最大長度為22, 但在函數中參數是否能超過22個我自己沒測試過,也無法保證,但可以確定的是一個函數不應該有這麼多個參數,你應該可以拆成更多個小函數去分擔運算邏輯。

現在讓我們來看看Example 3該如何轉換吧!

// Example 3
val sumOfSquares:(Int,Int)=> Int= (x,y)=>square(x)+square(y)

總結

在這個章節我們已經了解可以使用defval兩種方法在Scala中宣告函數,
其中最大的不同在於def可以省略回傳類型,但val用於宣告函數時,則必須指定函數類型,如Int=>Boolean
另外,Scala是可以在函數中再宣告子函數,同樣具備Closure的性質。
在一個章節,我們將會討論遞迴函數,一起來體會Scala中優美的函數式編程。

 
over 1 year ago

問題描述

#50.Pow(x, n)

func myPow(x float64, n int) float64 {
  
}

難度中
實作次方函數Pow(x,n),
若以數學式表示如下

解題思路

在這裡我們會用到次方函數以下幾點特性

  1. 任意數的0次方,皆等於1
  2. x的-1次方會等於1/x
  3. 次方數是可以加總的 根據特性1, 我們已經可以寫出第一行代碼了,如下
    if n==0{
        return 1
    }
    
    接著我們要來處理n為負數的情境,由特性2可知若n為負數時,可將x轉換為倒數, 代碼表示如下
    if n<0{
        x=1/x //x轉換為倒數
    
        n=-n  //n轉換為正數
    
    }
    

最後一步,使用遞迴開始運算,以數學式(1)表示

程式碼實作如下,

if n==0{
        return 1
    }
if n<0{
    x=1/x
    n=-n
  }
return x*myPow(x,n-1) //遞迴,n每次減1直到n=0時回傳結果

現在可以將代碼提交到LeetCode,按下右下角Submit Solution,LeetCode會自動幫你跑測試,如果沒有意外的的話,你應該會出現 Time Limit ExceededMemory Limit Exceeded等錯誤訊息.

表示在x=0.00001, n=2147483647程式運算太久或是發生了Stack Overflow!!!

現在我們要來改善這個問題,別忘了我們還有特性3還沒使用,我們將利用次方加總的特性減化運算過程, 將數學式(1)修改為

如此一下程式效能將大幅提升, 程式碼如下,

if n==0{
        return 1
    }
if n<0{
    x=1/x
    n=-n
  }
  

if n%2==0 {
        return myPow(x*x,n/2)
    }
return x*myPow(x*x,n/2) //由於n是Int,所以(n-1)/2與n/2結果會是相同

最後再重新提交一次吧


所以測試均通過,點擊More Details可以查看更多資訊

如上圖,我們通過300個test case,運行時間3ms, 打敗6.25%Golang的使用者,更多細節可以自己玩玩看
Go版本完整程式碼

Scala實作

 
  def myPow(x:Double,n:Long):Double={

    n match {
      case 0=>1
      case i if i<0=>myPow(1/x,-n) //與Go最大差別在於Scala無法對變數reassign,因此直接跑遞迴
      case i if i%2==0=>myPow(x*x,n/2) 
      case _=> x* myPow(x*x,n/2)
    }


  }

Scala版本完整程式碼

 
over 1 year ago

什麼是LeetCode

LeetCode是一個編程的交流平台,在上面超過了450個問題,包含不少算法及資料結構的題目,大家可以一起交流解法。目前LeetCode上支持C, C++, Java, Python, C#, JavaScript, Ruby, Swift, Go, Bash, MySQL等11種語言(沒有Scala,殘念!!),大家可以用自己擅長的語言去解題,系統還會幫你計算相同語言使用者的效能排名。
由於LeetCode目前還沒支持Scala,所以這系列文章將會用Go來刷LeetCode上的題目,通過LeetCode上的測試後,會在寫一下Scala的版本,畢竟Scala一直都是我的最愛XD

接下來就讓我們開始來玩LeetCode吧!!

LeetCode

  • LeetCode 登入畫面
    你可以選擇創建一個新的用戶,或是選擇右下解其他的登入方式,如FB,Google,LinkedIn以及Github(全球最大男性交友平台)等,我自己是用GitHub登入的。
  • 滿滿的問題列表
    LeetCode上的問題主要分成3種難度(Diffculty):簡單,中等,困難;Frequency應該表示的是面試考題出現的頻率,付費用戶才看的到。免費用戶也還是可以解題的。 接著就選擇你有興趣的問題開始玩玩看吧!

接下來的文章內容,我將專注在解題思路上,大家一起討論吧!!!

 
over 2 years ago

pattern matching算是Scala中的一大特色, 比起以往使用的if else或是switch-case有著更強大且優美的能力,
以下我將Scala的Pattern Matching使用方法分為4個部份,由簡單到因難依序介紹。

傳統方法

以下代碼示範了一個類似if else的例子,我們可以藉這個例子來了解patten matching的結構,

def toYesOrNo(choice: Int): String = choice match {
    case 1 => "yes"
    case 0 => "no"
    case _ => "error"
  }

// toYesOrNo(1)=>"yes"
// toYesOrNo(0)=>"no"
// toYesOrNo(33)=>"error"

_表示任意的情形, 若不想使用_也可以寫成以下的形式,

def toYesOrNo(choice: Int): String = choice match {
    case 1 => "yes"
    case 0 => "no"
    case whaterver => "whaterver "
  }

類型模式

除了判斷數值外,也可以判斷類型,如下,

def f(x: Any): String = x match {
    case i:Int => "integer: " + i
    case _:Double => "a double"
    case s:String => "I want to say " + s
  }

// f(1) → “integer: 1″Typ
// f(1.0) → “a double”
// f(hello)  I want to say hello

Functional approach to pattern matching

以下是一個Factorial的傳統遞迴方法

def fact(n: Int): Int ={
    if (n == 0) 1
    else n * fact(n - 1)
  }

改以pattern matching來實現, 又會如何呢??

def fact(n: Int): Int = n match {
    case 0 => 1
    case n => n * fact(n - 1)
  }

我們甚至可以限定n的範圍,如

    case n if (n>0)=>n * fact(n - 1)

模式匹配與集合

來試試一個集合加總的遞迴實現, 我們可能會寫出以下的代碼

def length[A](list : List[A]) : Int = {
    if (list.isEmpty) 0
    else 1 + length(list.tail)
  }

看起來沒什麼問題, 但在pattern matching下有更酷的寫法,

def length[A](list : List[A]) : Int = list match {
    case _ :: tail => 1 + length(tail)
    case Nil => 0
  }

Nil 代表集合為空時,

_::tailX 應該被理解成, “a list with whatever head followed by a tail.”我的解釋是能將一個list拆分為list.head與list.tail

總結

最後,我們用以下的例子總結我們在這篇文章提到的所有技巧

def parseArgument(arg : String, value: Any) = (arg, value) match {
  case ("-l", lang) => setLanguageTo(lang)
  case ("-o" | "--optim", n : Int) if ((0 < n) && (n <= 5)) => setOptimizationLevelTo(n)
  case ("-o" | "--optim", badLevel) => badOptimizationLevel(badLevel)
  case ("-h" | "--help", null) => displayHelp()
  case bad => badArgument(bad)
}

了解Pattern Matching後,在下一篇我們將與case class結合,看看能產生什麼樣的火花。

 
over 2 years ago

我們在前篇如何在Scala中實現合成函數中實現下方的函數,
$$f(1,10,g(x))=\sum_{x=1}^{10}g(x),\ where\ g(x)=x\ or\ x^2$$
程式碼如下,

def f(a:Int,b:Int,g:Int=>Int):Int=
{
    if (a>b) 0
    else  f(a+1,b,g)+g(a)
}
val fc =f(1,10,_:Int=>Int)

值得一提的是在這裡fc被稱為partially function
而partially function及currying常常放在一起討論,
主要原因在於兩者常能結合一起使用,使代碼更簡潔優美.
本篇文章分為三個部份

  • 1. 什麼是currying
  • 2. Scala中的currying
  • 3. currying & partially function

什麼是Currying

在Wiki是這樣描述的"currying is the technique of translating the evaluation of a function that takes multiple arguments (or a tuple of arguments) into evaluating a sequence of functions, each with a single argument."
換句話說,currying主要是將多個參數的函數轉換為只能接收一個單一參數的函數,舉列來說,

def sumOfSquares(x:Int,y:Int):Int=(Math.pow(x,2)+Math.pow(y,2)).toInt

p.s. 這裡使sumOfSquares回傳類型Int其實是沒有必要的,但我們最後會為各位示範currying + partially function,就讓我這麼做吧!!
sumOfSquares(2,3)轉換為sumOfSquares(2)(3)這樣的過程即稱為currying
反之則稱為uncurrying

Scala中的Currying

在Scala中創建currying函數有兩種方式,
第一種以def f(arg1:Type)(agrg2:Type)宣告即可。 如下

def sumOfSquares_Currying(x:Int)(y:Int):Int=(Math.pow(x,2)+Math.pow(y,2)).toInt
sumOfSquares_Currying(2)(3)

另一種創建方式主要是針對已存在的函數做Currying, 如以下代碼

val ss:(Int, Int) => Int=sumOfSquares_Currying(_:Int)(_:Int)
val ss_curried=ss.curried

相當簡單吧!!我們現在已經知道如何在Scala中創建currying函數,它該如何與我們最一開始使到partially function結合呢??

Currying & Partially

在Currying中使用Partially

若想在currying函數中使用partially,就像對一般函數一樣,在還不想給定參數的位置使用_即可, 但不同的是一般函數使用partially必須宣告_`的型別否則會出錯,而在currying函數中並不需要宣告,如下

sumOfSquares_Currying(2)(_) //OK
sumOfSquares_Currying(2)(_:Int) //OK

sumOfSquares(2,_)
//error message: missing parameter type for expanded function ((x$1) => sumOfSquares(2, x$1)) sumOfSquares(2,_)
sumOfSquares(2,_:Int) //OK

在Partially中使用Currying

試著思考一下,我們該如何利用Currying想實現以下的函數h
$$g(x,y)=x^2+y^2$$
$$f(1,10,g(x,2))=\sum_{x=1}^{10}g(x,2)$$
函數f(1,10,g(x,2))即為文章一開始提到的partially function val fc =f(1,10,_:Int=>Int); 函數g即為上述的sumOfSquares_Currying,現在讓我們來看看,如何一行指令結合fcsumOfSquares_Currying實作出上述等式

fc(sumOfSquares_Currying(2))

由於fc的型別為(Int => Int) => Int, 而sumOfSquares_Currying(2)則為Int => Int,因此我們將sumOfSquares_Currying(2)作為fc的參數實現上述的等式。

總結

在這篇文章中,我們提到了currying & partially function,並討論如何將它們結合起來一起使用,大家可以慢慢開始體會到Scala有趣(?)的地方了!!
Scala靈活的語法是它的特色之一,如果你對Scala有什麼好的想法,歡迎留言,我們下次見!!

參考文獻

如何在Scala中實現合成函數
Currying - Wikipedia
The Neophyte's Guide to Scala Part 11: Currying and Partially Applied Functions

 
over 2 years ago

什麼是合成函數(fucntion composition)

在Wiki的定義中是這麼描述的-"In mathematics, function composition is the pointwise application of one function to the result of another to produce a third function."
簡單的方式可以理解成函數的參數也為函數,這句話有點饒口對吧!!舉例來說,
$$\sum_{a}^{b}g(x)$$

這是一個常見的加總運算,其中a, b, g(x)均為這個加總運算的參數,若我們想以函數表示,則可以表示為
this is common summation function, where a, b, and g(x) are parameters of the function. if we want to notice
$$f(a,b,g(x))=\sum_{a}^{b}g(x)$$
f(a,b,g(x))即為一個合成函數.

Scala中的函數

在Scala中可以使用I=>O表示為一個參數型別為I,回傳型別為O的函數,如

val f1:Double=>Double=x=>Math.pow(x) //f1(x)=x^2
val f2:(Double,Double)=>Double=(x,y)=>Math.pow(x,2)+Math.pow(y,2) //f2(x)=x^2+y^2

其中x, y可用任意變量名表示.
到目前為止,可能有人已經想到如何在Scala中實現合成函數了,但在此之前,我們先以遞迴的方式實作加總運算函數f(a,b,g(x)),

def f(a:Int,b:Int,g:Int=>Int):Int=
{
    if (a>b) 0
    else  f(a+1,b,g)+g(a)
}

注意
在這裡我限制了g(x)的參數(x)及輸出值均為整數類型(Int=>Int)。

val constant:Int=>Int=x=>x
val pow:Int=>Int=x=>Math.pow(x,2).toInt //pow is a function that Int to Int

f(1,10,constant) 
f(1,10,pow)

等等!!這樣就就結束了嗎??當然沒有,在Scala中我們還可以使用更簡潔的寫法,

val fc: ((Int) => Int) => Int =f(1,10,_)
//or
val fc =f(1,10,_:Int => Int)

這裡我們用"_"取代了g:Int=>Int, fc的型別為((Int) => Int) => Int, 我們可以將fc理解為參數型別(Int) => Int,回傳型別Int的函數. 這樣做的好處在於可以減少代碼的重複性, 如下

fc(constant) //as like f(1,10,constant) 
fc(pow) //f(1,10,pow) 

注意
以下的寫法會造成編譯失敗,因為編譯器不知道""是什麼型別,所以必須指定的型別才能編譯通過

val fc =f(1,10,_)

http://www.elasticmining.com/blog/