Haskell 기능 적용 및 커링

Haskell 기능 적용 및 커링

---

저는 항상 새로운 언어를 배우는 데 관심이 있습니다.이 사실은 저를 계속해서 더 나은 프로그래머로 만듭니다. Haskell을 정복하려는 나의 시도는 지금까지 두 번왔다 갔다했고 나는 다시 시도 할 때라고 결정했습니다. 세 번째가 매력이지?

아니. 나는 내 오래된 노트를 다시 읽었고 실망했습니다 :-(

지난번에 제가 믿음을 잃게 만든 문제는 쉬운 것입니다. 정수의 순열이었습니다. 즉, 정수 목록에서 목록 목록으로-순열 목록 :

[int] -> [[int]]

이것은 사실 일반적인 문제이므로 위의 'int'를 'a'로 대체해도 여전히 적용됩니다.

내 노트에서 :

먼저 직접 코딩하면 성공합니다. 만세!

저는 저의 좋은 친구 인 Haskell 전문가에게 솔루션을 보냅니다. 일반적으로 전문가로부터 배우는 데 도움이됩니다. 그는 "언어의 진정한 힘, 일반 기능을 사용하여 코드를 작성하는 것을 표현합니다. 필요 ". 모든 것을 위해 최근에 쿨 에이드를 마 셨습니다.

permute :: [a] -> [[a]]
permute = foldr (concatMap.ins) [[]]
   where ins x []     = [[x]]
         ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]

흠. 이것을 분해 해보자 :

bash$ cat b.hs
ins x []     = [[x]]
ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]

bash$ ghci
Prelude> :load b.hs
[1 of 1] Compiling Main             ( b.hs, interpreted )
Ok, modules loaded: Main.

*Main> ins 1 [2,3]
[[1,2,3],[2,1,3],[2,3,1]]

좋아, 지금까지 아주 좋아. "ins"의 두 번째 줄을 이해하는 데 잠시 시간이 걸렸지 만 OK : 목록의 가능한 모든 위치에 첫 번째 인수를 배치합니다. 멋있는.

이제 foldr와 concatMap을 이해합니다. "Real world Haskell"에서 DOT가 설명되었습니다 ...

(f . g) x

...에 대한 또 다른 구문으로 ...

f (g x) 

그리고 전문가가 보낸 코드에서 DOT는 폴더에서 사용되었으며 "ins"기능은 "collapse"로 접습니다.

*Main> let g=concatMap . ins
*Main> g 1 [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]

좋아, 전문가가 DOT를 어떻게 사용하는지 이해하고 싶기 때문에 DOT 정의에 따라 동등한 표현을 시도합니다. (f .g) x = f (gx) ...

*Main> concatMap (ins 1 [[2,3]])

<interactive>:1:11:
     Couldn't match expected type `a -> [b]'
            against inferred type `[[[t]]]'
     In the first argument of `concatMap', namely `(ins 1 [[2, 3]])'
     In the expression: concatMap (ins 1 [[2, 3]])
     In the definition of `it': it = concatMap (ins 1 [[2, 3]])

뭐!?! 왜? 좋습니다. concatMap의 서명을 확인하고 람다와 목록이 필요하다는 것을 알았습니다.하지만 그것은 단지 인간의 생각입니다. GHC는 어떻게 대처합니까? 위의 DOT 정의에 따르면 ...

(f.g)x = f(g x), 

... 내가 한 일은 타당하고 대체 방식이었습니다.

(concatMap . ins) x y = concatMap (ins x y)

머리를 긁는 중 ...

*Main> concatMap (ins 1) [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]

그래서 ... DOT 설명은 분명히 너무 단순했습니다 ... DOT는 우리가 실제로 "인"이 카레를 빼고 첫 번째 주장을 "먹기"를 원했다는 것을 이해할만큼 충분히 영리해야합니다. 는 [t]에서 작동하려고합니다 (그리고 가능한 모든 위치에서 '1'로 "간섭").

그러나 이것은 어디에서 지정 되었습니까? 우리가 호출했을 때 GHC는 이것을 어떻게 알았습니까?

*Main> (concatMap . ins) 1 [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]

"ins"서명이 어떻게 든 이것을 전달 했습니까?

*Main> :info ins
ins :: t -> [t] -> [[t]]        -- Defined at b.hs:1:0-2

특별한 것은 없습니다. "ins"는 't', 't'목록을 취하고 모든 "interspersals"목록을 생성하는 함수입니다. "당신의 첫 번째 논쟁을 먹고 그것을 없애 버리는 것"에 대해서는 아무것도 없습니다.

그래서 ... 난 당황스러워. 나는 (코드를보고 한 시간 후에!) 무슨 일이 벌어지고 있는지 이해하지만 ... 전능하신 신 이시여 ... 아마도 GHC가 얼마나 많은 논쟁을 "벗겨 낼 수 있는지"보려고 시도할까요?

  let's try with no argument "curried" into "ins",
  oh gosh, boom, 
  let's try with one argument "curried" into "ins",
  yep, works,
  that must be it, proceed)

다시-yikes ...

그리고 내가 배우는 언어를 이미 알고있는 것과 항상 비교하고 있기 때문에 파이썬에서 "ins"는 어떻게 보일까요?

a=[2,3]
print [a[:x]+[1]+a[x:] for x in xrange(len(a)+1)]

[[1, 2, 3], [2, 1, 3], [2, 3, 1]]

솔직히 말해서 ... 어느 것이 더 간단합니까?

내 말은, 내가 Haskell의 초보자라는 것을 알고 있지만 바보처럼 느껴집니다 ... 한 시간 동안 4 줄의 코드를보고 컴파일러가 ... 뭔가를 찾을 때까지 다양한 해석을 시도합니다. " 클릭 "?

치명적인 무기에서 인용하자면, "나는 이것에 너무 늙었다"...

---

(f . g) x = f (g x)

사실입니다. 당신은 그로부터 결론을 내 렸습니다.

(f . g) x y = f (g x y)

또한 사실이어야하지만 그렇지 않습니다. 사실 다음은 사실입니다.

(f . g) x y = f (g x) y

동일하지 않습니다.

이것이 사실 인 이유는 무엇입니까? 음 (f . g) x y은과 동일하며 ((f . g) x) y우리가 그것을로 (f . g) x = f (g x)줄일 수 있다는 것을 알고 있기 때문에 (f (g x)) y다시 f (g x) y.

그래서 (concatMap . ins) 1 [[2,3]]동일합니다 concatMap (ins 1) [[2,3]]. 여기에는 마술이 없습니다.

이에 접근하는 또 다른 방법은 유형을 사용하는 것입니다.

. has the type (b -> c) -> (a -> b) -> a -> c, concatMap has the type (x -> [y]) -> [x] -> [y], ins has the type t -> [t] -> [[t]]. So if we use concatMap as the b -> c argument and ins as the a -> b argument, then a becomes t, b becomes [t] -> [[t]] and c becomes [[t]] -> [[t]] (with x = [t] and y = [t]).

So the type of concatMap . ins is t -> [[t]] -> [[t]], which means a function taking a whatever and a list of lists (of whatevers) and returning a list of lists (of the same type).

---

I'd like to add my two cents. The question and answer make it sound like . is some magical operator that does strange things with re-arranging function calls. That's not the case. . is just function composition. Here's an implementation in Python:

def dot(f, g):
    def result(arg):
        return f(g(arg))
    return result

It just creates a new function which applies g to an argument, applies f to the result, and returns the result of applying f.

So (concatMap . ins) 1 [[2, 3]] is saying: create a function, concatMap . ins, and apply it to the arguments 1 and [[2, 3]]. When you do concatMap (ins 1 [[2,3]]) you're instead saying, apply the function concatMap to the result of applying ins to 1 and [[2, 3]] - completely different, as you figured out by Haskell's horrendous error message.

UPDATE: To stress this even further. You said that (f . g) x was another syntax for f (g x). This is wrong! . is just a function, as functions can have non-alpha-numeric names (>><, .., etc., could also be function names).

---

You're overthinking this problem. You can work it all out using simple equational reasoning. Let's try it from scratch:

permute = foldr (concatMap . ins) [[]]

This can be converted trivially to:

permute lst = foldr (concatMap . ins) [[]] lst

concatMap can be defined as:

concatMap f lst = concat (map f lst)

The way foldr works on a list is that (for instance):

-- let lst = [x, y, z]
foldr f init lst
= foldr f init [x, y, z]
= foldr f init (x : y : z : [])
= f x (f y (f z init))

So something like

permute [1, 2, 3]

becomes:

foldr (concatMap . ins) [[]] [1, 2, 3]
= (concatMap . ins) 1 
    ((concatMap . ins) 2
       ((concatMap . ins) 3 [[]]))

Let's work through the first expression:

(concatMap . ins) 3 [[]]
= (\x -> concatMap (ins x)) 3 [[]]  -- definition of (.)
= (concatMap (ins 3)) [[]]
= concatMap (ins 3) [[]]     -- parens are unnecessary
= concat (map (ins 3) [[]])  -- definition of concatMap

Now ins 3 [] == [3], so

map (ins 3) [[]] == (ins 3 []) : []  -- definition of map
= [3] : []
= [[3]]

So our original expression becomes:

foldr (concatMap . ins) [[]] [1, 2, 3]
= (concatMap . ins) 1 
    ((concatMap . ins) 2
       ((concatMap . ins) 3 [[]]))
= (concatMap . ins) 1 
    ((concatMap . ins) 2 [[3]]

Let's work through

(concatMap . ins) 2 [[3]]
= (\x -> concatMap (ins x)) 2 [[3]]
= (concatMap (ins 2)) [[3]]
= concatMap (ins 2) [[3]]     -- parens are unnecessary
= concat (map (ins 2) [[3]])  -- definition of concatMap
= concat (ins 2 [3] : [])
= concat ([[2, 3], [3, 2]] : [])
= concat [[[2, 3], [3, 2]]]
= [[2, 3], [3, 2]]

So our original expression becomes:

foldr (concatMap . ins) [[]] [1, 2, 3]
= (concatMap . ins) 1 [[2, 3], [3, 2]]
= (\x -> concatMap (ins x)) 1 [[2, 3], [3, 2]]
= concatMap (ins 1) [[2, 3], [3, 2]]
= concat (map (ins 1) [[2, 3], [3, 2]])
= concat [ins 1 [2, 3], ins 1 [3, 2]] -- definition of map
= concat [[[1, 2, 3], [2, 1, 3], [2, 3, 1]], 
          [[1, 3, 2], [3, 1, 2], [3, 2, 1]]]  -- defn of ins
= [[1, 2, 3], [2, 1, 3], [2, 3, 1], 
   [1, 3, 2], [3, 1, 2], [3, 2, 1]]

Nothing magical here. I think you may have been confused because it's easy to assume that concatMap = concat . map, but this is not the case. Similarly, it may seem like concatMap f = concat . (map f), but this isn't true either. Equational reasoning will show you why.

참고URL : https://stackoverflow.com/questions/3884121/haskell-function-application-and-currying