एक पाश आधारित कार्यान्वयन

Question

लिए एक पुनरावर्ती कार्यान्वयन परिवर्तित मैं दो इंटरफेस है जो एक बंद

यहाँ आयोजित करने के लिए जिम्मेदार है है बंद पकड़े जब यह किसी नक्शे आपरेशन के लिए आता है के लिए पहले से एक है।

package com.fs; 

/** 
* This interface is responsible for holding the closures when it comes to map. 
* It uses two generic types. One for the argument and one for the return type. 
* @param <B> Generic type 
* @param <A> Generic type 
*/ 
public interface Func<B,A> { 
    /** 
    * Function prototype m takes an argument of type A and returns a type B. 
    * A map operation can produce a different type. 
    * @param x of type A 
    * @return type B 
    */ 
    B m(A x); 
} 

और छानने के संचालन

package com.fs; 


/** 
* This interface is responsible for holding the closures when it comes to filter. 
* @param <A> Generic type 
*/ 
public interface Pred<A> { 
    /** 
    * Function prototype m takes an argument of type A and returns a boolean. 
    * A filter operation checks every element if it fits a predicate. 
    * @param x of type A 
    * @return boolean 
    */ 
    boolean m(A x); 
} 

मैं एक वर्ग नामित CList जो बंद होने के साथ काम करने में सक्षम है है के लिए एक दूसरे के।

package com.impl.list; 

import com.fs.*; 

public class CList<T> { 
    T head; 
    CList<T> tail; 

    public CList(T x, CList<T> xs){ 
     head = x; 
     tail = xs; 
    } 

    static <A,B> CList<B> map(Func<B,A> f, CList<A> xs){ 
     if(xs==null){ 
      return null; 
     } 
     return new CList<>(f.m(xs.head),map(f,xs.tail)); 
    } 

    static <A,B> CList<B> maploop(Func<B,A> f, CList<A> xs){ 
     //????? 
     return null; 
    } 

    static <A> CList<A> filter(Pred<A> f, CList<A> xs){ 
     if(xs == null){ 
      return null; 
     } 
     if(f.m(xs.head)){ 
      return new CList<>(xs.head, filter(f,xs.tail)); 
     } 
     return filter(f,xs.tail); 
    } 

    static <A> int length(CList<A> xs){ 
     int ans =0; 
     while(xs!= null){ 
      ++ans; 
      xs=xs.tail; 
     } 
     return ans; 
    } 
} 

यहाँ मेरी सार्वजनिक बंद साथ CList को लागू करने इंटरफेस है।

package com.impl.list; 

import com.fs.Func; 
import com.fs.Pred; 

public class CListClient { 
    public static CList<Integer> doubleAll(CList<Integer> xs){ 
     Func<Integer, Integer> df = new Func<Integer, Integer>() { 
      @Override 
      public Integer m(Integer x) { 
       return x * 2; 
      } 
     }; 

     return CList.map(df, xs); 
    } 

    public static int countNs(CList<Integer> xs,final int n){ 
     Pred<Integer> pf = new Pred<Integer>() { 
      @Override 
      public boolean m(Integer x) { 
       return x==n; 
      } 
     }; 
     return CList.length(CList.filter(pf, xs)); 
    } 

    public static CList<Integer> doubleAllloop(CList<Integer> xs){ 
     Func<Integer, Integer> df = new Func<Integer, Integer>() { 
      @Override 
      public Integer m(Integer x) { 
       return x * 2; 
      } 
     }; 

     return CList.maploop(df, xs); 
    } 
} 

और एक सरल परीक्षक:

package basic; 


import com.impl.list.CList; 
import com.impl.list.CListClient; 
import org.junit.Test; 


public class ListTester { 

    CList<Integer> intlist_1 = new CList<>(new Integer(1),null); 
    CList<Integer> intlist_2 = new CList<>(new Integer(2),intlist_1); 
    CList<Integer> intlist_3 = new CList<>(new Integer(3),intlist_2); 
    CList<Integer> intlist_4 = new CList<>(new Integer(4),intlist_3); 
    CList<Integer> intlist_5 = new CList<>(new Integer(4),intlist_4); 
    CList<Integer> intlist = new CList<>(new Integer(5),intlist_5); 

    @Test 
    public void test_doubleAll(){ 
     CList<Integer> doubled = CListClient.doubleAll(intlist); 
     CList<Integer> doubledloop = CListClient.doubleAllloop(intlist); 

    } 

    @Test 
    public void test_CountNs(){ 
     int count3s = CListClient.countNs(intlist, 3); 
    } 
} 

मैं नक्शा समारोह जो थोड़ी देर के पाश करने के लिए एक पुनरावर्ती तरह से कार्यान्वित किया जाता है परिवर्तित करने के लिए कोशिश कर रहा हूँ। मैंने इसे maploop नाम दिया। यह मेरे दिमाग को दो दिनों तक दर्द देता है। कोई संकेत मुझे बहुत खुश कर देगा। मैं इस सवाल से यहां पूछ रहा हूं क्योंकि कोई संभावना है कि कोई दान ग्रॉसमैन कोर्स ले सकता है और उदाहरण देख सकता है और उस समारोह को लागू करने का प्रयास कर सकता है। मैं एक वास्तविक उत्तर से एक संकेत पसंद करते हैं। धन्यवाद।

Answer 1

एक पुनरावर्ती फ़ंक्शन को पुनरावर्तक फ़ंक्शन में कनवर्ट करते समय, आपको यह जांचना होगा कि कौन सी गैर पूंछ कॉल स्थिति आवश्यक है, यदि कोई हो। फिर एक ढेर बनाएं और राज्यों को ढेर पर धक्का दें, और कोड जैसे आप रिकर्सिव फ़ंक्शन अन्यथा करेंगे। यदि आपके पास फ़ंक्शन में एकाधिक रिकर्सिव कॉल हैं, तो आपको अपने नए स्टेट आइटम की आवश्यकता होगी जिसमें आपके द्वारा किए गए फ़ंक्शन में कौन सा बिंदु इंगित करने वाला मान भी शामिल होगा।

इस मामले में, आपके पास केवल एक रिकर्सिव कॉल है, और एकमात्र राज्य xs है, इसलिए चीजें बहुत सरल हैं और आपको कस्टम स्टेटस ऑब्जेक्ट की आवश्यकता नहीं है।

यहां बताया गया है कि मैं चीजें कैसे करता हूं (परीक्षण नहीं किया जाता)।

static <A,B> CList<B> maploop(Func<B,A> f, CList<A> xs){ 
    Stack<CList<A>> stack = new Stack<>(); 

    while(xs != null){ 
     stack.push(xs); 
     xs = xs.tail; 
    } 

    CList<a> result = xs; 

    while(!stack.empty()){ 
     xs = stack.pop(); 
     result = new CList<>(f.m(xs.head), result); 
    } 

    return result; 
}  

Answer 2

एक सतत एक के लिए एक पुनरावर्ती कार्यक्रम को बदलने के लिए मानक दृष्टिकोण, एक पूंछ पुनरावर्ती संस्करण के माध्यम से है। एक बहुत ही सरल उदाहरण के रूप में गणना करने के लिए N!, निम्नलिखित पुनरावर्ती भाज्य समारोह पर विचार करें:

int factorial(int x) { 
    if (x == 0) 
     return 1; 
    else 
     return x * factorial(x-1); 
} 

कॉल factorial(N);। आपकी समस्या

int x = N; 
int y = 1; 
while (x != 0) { 
    y = x*y; 
    x = x-1; 
} 

बेशक

,:

बनाना इस पूंछ पुनरावर्ती एक संग्रह चर जोड़ने शामिल है:

int tailRecursiveFactorial(int x, int y) { 
    if (x == 0) 
     return y; 
    else 
     return tailRecursiveFactorial(x-1, x*y); 
} 

कॉल tailRecursiveFactorial(N, 1);

यह एक सीधी एक सतत कार्यक्रम के लिए तब्दील हो जाता है एक अच्छा सौदा कठिन है, लेकिन सामान्य दृष्टिकोण अभी भी काम करना चाहिए।