하스켈에서 두 개의 다른 세트를 업데이트하는 동안 두 세트를 반복하십시오.

다음 명령형 코드를 하스켈의 기능적 솔루션으로 변환하려고합니다. 세트 s의 구성원을 s'의 구성원과 비교하고 비교를 기준으로 t 및 t' 업데이트 세트를 비교하려고합니다. S가 Data.Set을 입력이다 나는 기원하고 하스켈 함수의 유형은 무엇인가 등이있다하스켈에서 두 개의 다른 세트를 업데이트하는 동안 두 세트를 반복하십시오.

-- s, s', t, t' are of type Data.Set a 
-- foo x y returns a Just a or Nothing 
foo :: a -> a -> Just a 

-- Initialize t and t' to s and s' 
t = s 
t = s' 

foreach x in s 
    foreach y in s' 
     if (foo x y) == Just z 
     insert z into t 
     delete x from t 
     delete y from t' 

return (t, t')

mergeSets :: S.Set -> S.Set -> (S.Set, S.Set) 
mergeSets s s' = ...

와 함수의 결과 한 쌍 될 것입니다 : 여기에 필수적 의사입니다 새 세트 t 및 t' (또는 t 및 t' 두 세트를 모두 반환하는 다른 방법).

출처

2013-03-02 Neil

그것은'foo'가 do.'Returns 새로운 요소로 가정된다 알고 도움이 될 것이다 '는 약간 불분명하다. 세트 교차점 또는 노조를 찾으십니까? –

이것은 상당히 이상한 요구 사항입니다. 당신이 정말로하려고하는 것에 대해 더 많이 말한다면 (약간의 맥락은 좋을 것입니다), 우리는 대안적인 접근 방법을 제안 할 수있을 것입니다. –

당신의 의사 코드가 정확하지 않다고 믿는 경향이 있습니다. 그 결과는 두 세트의 순회 순서에 달려 있기 때문입니다. 나에게 그것은 실제로는 데카르트 곱을 만들고, 쌍을 처리 한 다음 결과 집합에서 특정 요소를 제거하려는 것 같다. – us2012

여기에 하나의 가능성이다. 위의 내용은 귀하가하지 않았다고 가정합니다. 당신의 세트는 어떤 큰 경우

, 당신은 썽크을 피하기 위해 엄격를 추가해야 할 수 있습니다 블로우 업 :

bar s s' = foldl (\ (t,t') (z,(x,y)) -> 
      let a=insert z t; b=delete x a; c=delete y t' 
      in a `seq` b `seq` c `seq` (b,c)) 
    ....

출처

2013-03-02 22:52:18

나는 간섭을 피하는 것이't'와't''를's'와's'로 초기화하고's'와's'를 반복하는 목적이라고 생각합니다. – luqui

@luqui 네 말이 맞아! 그런 다음 그 자격은 불필요합니다. (잘못 말했거나, OP의 의도에 대해 말 했어야했는지, 간섭을 의도했는지 여부, 루핑 업데이트 중). 하지만, 복사하는 것은 딥 카피 (deep copy)이든 아니든간에, 언어의 구현에 달려 있습니다. –

예,'t'와't'를 초기화하는 목적은 간섭을 피하기위한 것이 었습니다. 나는 아직도 폴드하는 데 익숙해 져있어 조금 더 오래 쳐다볼 필요가있다. 도움에 감사드립니다. – Neil

Set과 같은 콜렉션 데이터 유형으로 작업하는 경우 일반적으로 요소 위에 루프를 작성하지 않을 것입니다. 그것은 목록에 더 적합 할 것입니다. 따라서 알고리즘이 일부 중첩 된 방식으로 모든 요소를 열거해야하는 경우 집합을 a list.

으로 변환합니다. 따라서 중첩 루프를 완전히 집합에 사용하지 않고 대신 집합의 선언적 사양을 찾습니다. 작업 : 교차로, 노동 조합 등의 차이를 제공 할 수없는 경우 목록에 순진 번역은 확실히 가능하다

: 간단한 비트가 중첩 루프를 모델링한다

import qualified Data.Set as S 

mergeSets :: Ord a => S.Set a -> S.Set a -> (S.Set a, S.Set a) 
mergeSets s t = go1 (S.toList s) s t 
    where 
     go1 []  t t' = (t,t') 
     go1 (x:xs) t t' = go1 xs u u' 
      where 
       (u, u') = go2 x (S.toList t) t t' 

     go2 x []  t t'  = (t,t') 
     go2 x (y:ys) t t' 
      | Just z <- foo x y = go2 x ys (S.delete x (S.insert z t)) (S.delete y t') 
      | otherwise   = go2 x ys t t' 

-- for example 
foo x y = if x == y then Just x else Nothing

. 예를 들어 목록 이해력. 그러나 algo는 출력 집합의 변이를 사용하므로이를 누적 매개 변수로 전달해야합니다.

실제로 하스켈을 멋지게 이해하려면 요소 별 명령형 스타일을 포기하고 자연스러운 Set api의 관점에서 작업해야합니다. 좋은 해결책을 제시하는 길입니다.

bar s s' = 
    foldl (\ (t,t') (z,(x,y)) -> 
       (delete x (insert z t) , delete y t')) 
    (s,s') 
    [(z,(x,y)) | x <- toList s, y <- toList s', Just z <- [foo x y]]

여기에 주요 질문은 당신의 삽입과 삭제가 foreach 메커니즘을 방해 할 의도 여부 :

출처

2013-03-02 22:52:08

나는 이것이 효과가있을 것이라고 생각한다. 나는 한 발을 내줄 것이다. 고맙습니다. – Neil

아마 당신은'(u, u ') = go2 x (S.toList t') t t''를 의미할까요? –

하스켈에서 두 개의 다른 세트를 업데이트하는 동안 두 세트를 반복하십시오.

답변

관련 문제