मैं केवल हास्केल सीखने की शुरुआत में हूं, और वर्तमान में मैं सूचियों की संभावनाओं की खोज कर रहा हूं। मैं दो सूचियों का योग करना चाहता था, लेकिन किसी तरह यह गलत हो गया।

इसलिए:

इनपुट: sumTwoLists [२,५,७,७,९] [१,२,२] (मूल रूप से २५७७९ + १२२)

आउटपुट: [२,५,९,०,१]

सबसे पहले, मैंने पूरी सूची को उलट दिया, क्योंकि बहु-अंकीय संख्याओं का जोड़ अंत में शुरू होना चाहिए:

reverseList :: [Int] -> [Int]
reverseList [] = []
reverseList (x:xs) = reverseList xs ++ [x]

यह काम करता है। फिर मैंने एक ऐड फंक्शन लागू किया:

add :: (Num a) => [a] -> [a] -> [a]
add _ [] = []
add [] _ = []
add (x:xs) (y:ys) = (x + y) : add xs ys

लेकिन जब एक सूची छोटी होती है, तो दूसरी सूची गलत हो जाती है। (जोड़ें [२,५,७,७,९] [१,२,२] = [३,७,९]) तो फिक्शन को भी निचली संख्या के अंत में ० जोड़ना होगा ([१,२,२] = [1,2,2,0,0]।)

और उसके बाद मैंने sumTwoLists फ़ंक्शन को इस तरह लागू करने का प्रयास किया:

sumTwoLists :: [Int] -> [Int] -> [Int]
sumTwoLists (x:xs) (y:ys) = reverseList ((reverseList (x:xs)) add (reverseList (y:ys)))

लेकिन यह कोड इस तथ्य को ध्यान में नहीं रखता है कि तत्व 9 से अधिक नहीं हो सकते हैं। मैं तत्वों को Int या Integer में नहीं बदलना चाहता, इसलिए मैं उनमें से किसी का भी उपयोग नहीं करता।

मैं मूल रूप से सूचियों को उलटना चाहता हूं, फिर सबसे छोटी सूची में 0 जोड़ें, फिर प्रत्येक तत्व को दूसरी सूची से एक तत्व के साथ जोड़ दें और यदि परिणाम> 9 है, तो परिणाम 10 (मॉड?) आसन्न संख्या में वृद्धि हुई है

किसी भी मदद के लिए मैं बहुत आभारी रहूंगा!

1
Theresa 10 जिंदा 2021, 14:37

3 जवाब

सबसे बढ़िया उत्तर

सूचियों के साथ ऐसा करने का कोई मतलब नहीं है, क्योंकि यह बहुत सारी अतिरिक्त समस्याएं पेश करेगा:

  1. शून्य के साथ पैडिंग यदि दो सूचियों की लंबाई समान नहीं है, या यदि योग को एक अतिरिक्त तत्व की आवश्यकता है; तथा
  2. इस बात को ध्यान में रखते हुए कि दो अंकों को जोड़ने से मान 9 से अधिक हो सकता है और इस प्रकार कैरी का परिचय देता है।

add फ़ंक्शन ठीक से काम नहीं कर रहा है, क्योंकि यह किसी एक सूची के समाप्त होने के क्षण से रुक जाता है, इसके अलावा यह ध्यान नहीं देता है कि अंक "ओवरफ़्लो" हो सकते हैं। इस प्रकार हमें एक फ़ंक्शन add का निर्माण करना चाहिए जिसमें एक अतिरिक्त पैरामीटर हो: कैरी:

add' :: Int -> [Int] -> [Int] -> [Int]
add' 0 [] [] = []
add' n [] [] = [n]
add' n xs [] = add' n xs [0]
add' n [] xs = add' n [0] xs
add' n (x:xs) (y:ys) = r : add' q xs ys
    where (q,r) = quotRem (x+y+n) 10

add इस प्रकार कैरी के रूप में शून्य से शुरू होता है:

add :: [Int] -> [Int] -> [Int]
add = add' 0

यदि हम इस प्रकार उलटी सूचियों के योग की गणना करते हैं, तो हम प्राप्त करते हैं:

Prelude> add [9,7,7,5,2] [2,2,1]
[1,0,9,5,2]

इसे काम करने के लिए, आपको add को एक इंफिक्स ऑपरेटर के रूप में उपयोग करने की आवश्यकता है, और दो ऑपरेंड खाली या गैर-रिक्त सूचियां हो सकती हैं:

sumTwoLists :: [Int] -> [Int] -> [Int]
sumTwoLists xs ys = reverseList ((reverseList xs) `add` (reverseList ys))

या के साथ on :: (b -> b -> c) -> (a -> b) -> a -> a -> c:

import Data.Function(on)

sumTwoLists :: [Int] -> [Int] -> [Int]
sumTwoLists = add `on` reverse

दिए गए नमूना इनपुट के लिए, अब हम प्राप्त करते हैं:

Prelude> sumTwoLists [2,5,7,7,9] [1,2,2]
[2,5,9,0,1]

अंत में reverseList पहले से ही Prelude में मौजूद है: reverse :: [a] -> [a]. आपके द्वारा कार्यान्वित reverseList फ़ंक्शन O(n2) में चलता है, जो बहुत कुशल नहीं है, आप रैखिक समय प्राप्त करने के लिए एक संचायक का उपयोग कर सकते हैं।

3
Willem Van Onsem 12 जिंदा 2021, 23:48

यह आधार १० में एडिक योग है। यहाँ एक कार्यान्वयन है।

-- odometer (add one in base b)
odom :: Int -> [Int] -> [Int]
odom b (x : xs) | x<(b-1) = (x+1) : xs
                | xs==[] = [0,1]
                | otherwise = 0 : odom b xs

-- iterated odometer
odom_iter :: Int -> [Int] -> Int -> [Int]
odom_iter b t n | n == 0 = t
                | otherwise = odom b (odom_iter b t (n-1))

-- adic addition
sumadic :: Int -> [Int] -> [Int] -> [Int]
sumadic b (x:xs) (y:ys) | xs == [] = odom_iter b (y:ys) x
                        | ys == [] = odom_iter b (x:xs) y
                        | sumxy < b = (sumxy : (sumadic b xs ys))
                        | sumxy == b = (0 : (odom b (sumadic b xs ys)))
                        | otherwise = (1 : (odom b (sumadic b xs ys)))
                          where sumxy = x+y

यह सूचियों को उलट कर काम करता है:

> sumadic 10 [9, 7, 7, 5, 2] [2, 2, 1]
[1,0,9,5,2]

तो आपको बस sumadic को उलटी सूचियों में लागू करना होगा और आउटपुट को उल्टा करना होगा:

sumTwoLists x y = reverse $ sumadic 10 (reverse x) (reverse y)
2
Stéphane Laurent 10 जिंदा 2021, 15:14

यह उत्तर हास्केल बिल्ट इन का उपयोग करेगा अपनी reverseList के बजाय को उल्टा करें, हालांकि वे आपस में बदले जा सकते हैं।

आइए अपने ऐड फंक्शन को देखकर शुरू करें:

add :: (Num a) => [a] -> [a] -> [a]
-- look at these next 2 lines specfically
add _ [] = []
add [] _ = []
add (x:xs) (y:ys) = (x + y) : add xs ys

यदि आप एक खाली सूची में एक गैर-रिक्त सूची जोड़ रहे हैं, तो आपका वर्तमान कोड कहता है कि यह खाली सूची है, जो स्पष्ट रूप से सत्य नहीं है (add [1, 2, 3] [] [1, 2, 3] होना चाहिए)। तो, आप पहले दूसरी सूची लौटाकर अपने आधार मामलों को ठीक कर सकते हैं:

add :: (Num a) => [a] -> [a] -> [a]
-- return the other list
add [] x = x
add x [] = x
add (x:xs) (y:ys) = (x + y) : add xs ys

अगर आप दो खाली सूचियां हैं जोड़ रहे हैं, तो दूसरी सूची खाली सूची है, इसलिए आप अभी भी खाली सूची को सही ढंग से वापस कर रहे हैं। अब, हम संबोधित कर सकते हैं "यह कोड इस तथ्य को ध्यान में नहीं रखता है कि तत्व 9 से अधिक नहीं हो सकते" भाग। चूंकि आपके जोड़ने का तरीका यह अनुकरण कर रहा है कि आप पेन और पेपर पर कैसे जोड़ेंगे, इसे इसी तरह करना जारी रखें। यदि परिणाम, उदाहरण के लिए, 12 है, तो अंक 2 है और 1 ले जाया जाता है। याद रखें कि मॉड विभाजन का शेष भाग है, इसलिए 12 `mod` 10 (हास्केल में बैकटिक्स एक फ़ंक्शन को इनफिक्स बनाता है) 2 है, और 12 `div` 10, पूर्णांक विभाजन की प्रकृति के कारण नीचे की ओर पूर्णांकित होने के कारण, आपको पहले अंक के बाद प्रत्येक अंक देगा, जो कि 1 है।

बात करने के लिए पर्याप्त है, आइए कुछ कोड लिखें:

-- change Num to Integral because we need to work with integers
add :: (Integral a) => [a] -> [a] -> a -> [a]
--        we need to add a carry now ^
-- these base cases break down if carry is non-zero
add [] x c
    -- if carry is zero we're fine
    | c == 0    = x
    -- just add the carry in as a digit
    | otherwise = add [c] x 0
-- same applies here
add x [] c
    | c == 0    = x
    | otherwise = add x [c] 0
add (x:xs) (y:ys) c = dig : add xs ys rst
    where sum = x + y + c    -- find the sum of the digits plus the carry
          -- these two lines can also be written as (rst, dig) = sum `divMod` 10
          dig = sum `mod` 10 -- get the last digit
          rst = sum `div` 10 -- get the rest of the digits (the new carry)

और अब, आपका सहायक कार्य इसे प्रारंभिक कैरी के रूप में 0 के साथ कॉल कर सकता है:

addTwoLists :: (Num a) => [a] -> [a] -> [a]
addTwoLists x y = reverse $ add (reverse x) (reverse y) 0
2
Aplet123 10 जिंदा 2021, 15:30