Structural Typing과 Duck Typing

Posted 2011.04.15 16:23

Duck Typing

duck typing에 대한 정의는 duck test를 정의한 다음 문장에 잘 나타난다.
오리처럼 소리내고, 오리처럼 걷는다면 오리라고 불러도 무방하다.
좀 더 구체적으로 정의하면, 해당 객체의 타입을 이용해 객체의 적합성 여부를 검증하기 보다는, 특정 객체가 호출하려는 메세지를 이해할 수만 있다면 사용해도 좋은 객체로 간주하겠다는 의미이다. 위키피디아의 duck typing 설명에 의하면, 다음과 같이 "객체를 구성하는 메서드와 프로퍼티가 객체의 유효 여부를 결정한다"고 정의되어 있다.
an object's current set of methods and properties determines the valid semantics
개인적으로는 Objective-C와 같이 메시지 호출과 객체의 구성 요소(메서드 혹은 프로퍼티)가 동적으로 분리(dynamic dispatching)될 수 있는 언어를 고려하면, "객체가 메시지를 이해할 수 있다면 유효하다고 간주한다"는 말이 좀 더 정확하다고 생각한다. 메세지 디스패칭을  동적으로  정의할 수도 있기 때문이다.

사전 준비

다음과 같이 클래스 Fish, Duck, Person를 정의하자.
class Fish {
 def swim = println("fish: swim")
}

class Duck {
 def quack = println("duck: quaaaack")
 def feathers = println("duck: white feathers")
}

class Person {
 def think = println("person: therefore I am")
 def quack = println("person: speak qua~~ack!")
 def feathers = println("person: wear feather clothing")
}

Structural Typing

Scala에서는 Structural Typing으로 type safe한 방법의 Duck Typing을 지원한다. 다음과 같이 Structural Type을 이용해 DuckLike 타입을 선언하자. DuckLike 타입은 quack, feathers 메서드가 정의된 어떤 타입과도 호환된다.
type DuckLike = { def quack; def feathers } // Structural Typing

def inTheForest( duckLike: DuckLike ) {
  duckLike.quack
  duckLike.feathers
}

/*
scala> inTheForest( new Duck )  
duck: quaaaack
duck: white feathers

scala> inTheForest( new Person )
person: speak qua~~ack!
person: wear feather clothing

scala> inTheForest( new Fish )
<console>:9: error: type mismatch;
 found   : Fish
 required: DuckLike
       inTheForest( new Fish )
                    ^

*/
동적 타입 언어와는 달리 해당 메시지를 이해할 수 있는지 미리 검증한다는 점에서 검증 시점의 차이가 존재한다. Ruby나 Python, Objective-C와 같은 다른 언어에서의 duck typing은 소개한 위키피디아 링크에 나와 있으니 참고하자.
저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
 2010년 가을 무렵에 맹수님이 스칼라 스터디에서 출제했던 순열(permutation) 구하기 문제를 공유[각주:1]합니다. 당시 이 퀴즈를 풀기위해 점심 시간 한 번은 고민하느라, 또 한 번은 문제 푸느라 휙~ 보냈던 기억이 있어 지금도 이 순열 퀴즈를 '밥도둑'이라 부릅니다. 당연한 이야기이지만, 풀이 방법은 다양하므로 본문 내용은 참고로 보시면 됩니다.

문제

주어진 순열 문제는 다음과 같다.
임의의 알파벳 시퀀스를 입력받아서, 해당 알파벳으로 만들 수 있는 순서의 조합을 모두 구한다. 
그리고 결과는 문자열의 오름차순으로 정렬하여 출력한다. 
(예를 들어, "AB", "BA" 가 있는 경우 "AB"가 "BA"보다 먼저 나와야 한다.)

 ex)  "ABC" -> "ABC", "ACB", "BAC", "BCA", "CAB", "CBA"
      "AAB" -> "AAB", "ABA", "BAA"
      "ABA" -> "AAB", "ABA", "BAA"
      "000" -> "000"

목표코드의 형태

우선은 순열로 나타낼 대상 문자열을 List[Char]로 나타내고, List에 permutate라는 메서드를 추가해[각주:2] 다음과 같이 동작할 계획이다.
scala> "AB".toList.permutate
res8: List[List[Char]] = List(List(A, B), List(B, A))

scala> "ABB".toList.permutate
res9: List[List[Char]] = List(List(A, B, B), List(B, A, B), List(B, B, A))
순열은 여러 종류의 문자열이므로 permutate의 결과는 List의 List, 즉 List[List[Char]]이다.

순열 분석

"ABB"를 순열로 표현한다면 첫째 자리에는 3개의 글자 중 중복을 제거한 A 또는 B 두 가지만이 가능하다. 이를 Tree로 나타내면 다음과 같다.

A 혹은 B가 나왔다면 그 다음은 어떤 문자들이 나와야 할까를 고민하며 트리를 작성하다보니, 자식 노드들은 결국 부모 노드의 문자를 제외한 나머지 문자들의 순열이라는 사실을 알 수 있었다. 


다시 말해 1의 영역은 A를 제외한 나머지 원소들의 순열이고, 2의 영역은 B를 제외한 나머지 원소들의 순열이다. 예를 들어 부모 노드에서 A가 나오면 나머지 문자인 B, B로 구성된 순열은 1가지 뿐이다.  전체 순열은 "A + 영역1"과 "B+영역2"로 나타낼 수 있으므로, 이를 통해 순열 문제는 재귀적인 과정으로 풀 수 있다는 예측이 가능하다.

permutate 메서드의 작성

이제 트리를 코드로 표현해야 한다. 트리의 특정 문자열(예시의 경우 List("A","B","B"))의 순열은 결국 자신의 원소들을 중복 제거한 head와 head를 제외한 나머지 원소들의 순열로 표현된다. 이는 대강 다음과 같은 형태로 표현이 가능하다. 
def permutate(list:List[Char]):List[List[Char]] = {

  val heads:List[Char] = list.distinct       // 원소의 중복을 제거하는 distinct 메서드는 제공됨
  
  // heads loop {

    val tail = list.removeFirst( _ == head)  // 일치하는 조건의 원소를 단 하나만 지움(작성 예정)
    permutate(tail).map( head :: _ )         // 자식의 순열에 head를 결합하면 전체 순열이 됨

  // } loop end
완전하지 않은 코드이지만 핵심은 모두 담고 있다.

먼저 조건식 p와 일치하는 원소를 하나만 제거하는 removeFirst()를 작성하자.
def removeFirst[T](p:(T)=> Boolean):List[T] = {
  val index = list.indexWhere(p)
  val (first, _ :: second) = list.splitAt(index)
  first ::: second
}
내용은 간단하다. 조건식 p와 일치[각주:3]하는 원소의 위치를 찾아(indexWhere), 해당 위치를 기준으로 두 리스트로 쪼개고(splitAt), 패턴 매칭[각주:4]을 활용해 조건에 맞는 위치의 원소 하나를 제외한 앞 뒤 List를 합쳤다. 그 결과 찾아낸 원소가 제외된 리스트가 완성된다. 

핵심 메서드인 permutate의 구현은 다음과 같다. 중복 없는 head에 소트를 추가하는 등의 내용이 추가됐고, flatMap 등의 메서드가 머리를 어지럽게 할 수도 있지만  미리 작성해본 permutate 구현과 핵심적인 내용은 같다. 오히려 코드를 참고하지 않고 직접 작성해 보면 이해가 빠를지도 모르겠다.
def permutate(list:List[Char]):List[List[Char]] ={
val heads:List[Char] = list.distinct.sortWith(_ < _)
heads.flatMap( head => {
  val tail = list.removeFirst( _ == head)
  tail match {
	case Nil => List(List(head))
	case _ => permutate(tail).map ( head :: _ )
  }
})
}
마지막으로 List에 permutate 메서드(removeFirst 도 추가하려 한다)를 추가하기 위해 Implicit Type Conversion을 적용해 보자.

Implcit Type Conversion 적용

PermuatbleList 클래스에 순열을 만들기 위해 필요한 기능을 넣고 Implicit Type Conversion을 적용해 List의 기능을 확장할 계획이다. Implicit Type Conversion을 적용하려면 해당하는 implicit 메서드가 현재 scope에서 사용가능해야 한다.
object PermutableList {
  implicit def listToPermutableList(list:List[Char]):PermutableList = {
    new PermutableList(list)
  }
}
implicit 메서드가 위와 같이 선언되어 있을 경우, Implicit Type Conversion이 일어나게 하려면 다음 구문이 필요하다.
import PermutableList._

마무리

Implicit Type Conversion을 적용하고 정리한 최종 코드는 다음과 같다
package lasco.homework.nephilim.permutation

class PermutableList(val list:List[Char]) {
  def permutate():List[List[Char]] ={
    PermutableList.permutate(list)
  }

  def removeFirst[T](p:(T)=> Boolean):List[T] = {
    PermutableList.removeFirst(list)(p)
  }

}

object PermutableList {
  implicit def listToPermutableList(list:List[Char]):PermutableList = {
    new PermutableList(list)
  }

  def removeFirst[T](list:List[T])(p:(T)=> Boolean):List[T] = {
    val index = list.indexWhere(p)
    val (first, _ :: second) = list.splitAt(index)
    first ::: second
  }

  def permutate(list:List[Char]):List[List[Char]] ={
    val heads:List[Char] = list.distinct.sortWith(_ < _)
    heads.flatMap( head => {
      val tail = list.removeFirst( _ == head)
      tail match {
        case Nil => List(List(head))
        case _ => permutate(tail).map ( head :: _ )
      }
    })
  }
}

/*
//@ scala console
import lasco.homework.nephilim.permutation._
import PermutableList._

"A".toList.permutate
res7: List[List[Char]] = List(List(A))

"AB".toList.permutate
res8: List[List[Char]] = List(List(A, B), List(B, A))

"ABB".toList.permutate
res9: List[List[Char]] = List(List(A, B, B), List(B, A, B), List(B, B, A))
*/
  1. 사실 이번에도 묵은지 포스팅임. 본문은 2010년 9월 초에 임시 저장했던 글임. [본문으로]
  2. Implicit Type Conversion을 활용한다는 의미. 이렇게 Implicit Type Conversion은 기존 클래스 혹은 모듈의 기능 확장에 주로 사용됨. [본문으로]
  3. p는 predicate을 나타냄 [본문으로]
  4. val (first, _ :: second) = ... 에는 tuple pattern과 list pattern이 사용됨 [본문으로]
저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
« PREV : 1 : 2 : 3 : 4 : 5 : ... 44 : NEXT »

티스토리 툴바